Java教程

静态莫队分块

本文主要是介绍静态莫队分块,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

静态莫队分块

分块的另一种重要形式是对询问分块。这是一种离线做法,又被称为“莫队算法”(前国集队长莫涛在“小 Z 的袜子”一题中创造性的提出了这种做法,因此得名)。

在了解静态莫队算法之前,可以先思考这样一个问题:

  • 为什么在线的暴力算法很慢?

显然,对于每次询问,暴力算法都重新处理一遍答案,输出结果。由于没有数据结构的优化,导致效率很低。

莫队算法的本质也是暴力,但它的优点在于调整了询问出现的顺序,使得重复利用之前处理过的答案成为可能。

什么是莫队分块?什么是莫队分块?如果你想了解,莫队分块的话,现在就带你研究。

静态莫队原理

既然叫“静态莫队”,肯定是处理只有区间询问,没有修改的问题啦!

预处理

首先读入需要操作的数组 \(A\) 和操作序列 \(Q,(Q_i=[l_i,r_i])\),离线下来。

把数组 \(A\) 分成 \(\sqrt N\) 块,第 \(i\) 块记作 \(A_i\) ,再把所有询问 \(Q_j\) 按照左端点 \(l_j\) 从小到大排序,使每一个 \(Q_j\) 的 \(l_j\) 落在某个块 \(A_i\) 内(如果 \(Q_j\) 的左端点 \(l_j\) 落在 \(A_i\) 块内,那么记这个 \(Q_j\in A_i\))。然后把每个 \(A_i\) 块内包含的所有 \(Q_j\) 按照 \(r_j\) 从小到大排序。

复杂度分析

排序之后,在每块内部,两个相邻询问的左端点变化 \(<\sqrt N\) ,右端点变化单调递增。如果我们以上一次询问的回答为基础,那么每次最多花 \(\sqrt N\) 的时间处理两次询问左端不同的部分。而 \(A_i\) 整块内,右端点增长的范围之和 \(N\) 。

一共有 \(N\) 次询问 ,\(\sqrt N\) 个块需要处理,总共处理左端点 \(N\) 次乘 \(\sqrt N\) 处理一次,总共处理 \(\sqrt N\) 个块,处理一个块内的右端点总共花 \(N\) ,总复杂度 \(O(N\sqrt N)\) 。(实际上莫队跑得比这个快多了)

但是这个复杂度是建立在可以 \(O(1)\) 处理单个元素对答案的影响之上的。如果用莫队套了某种数据结构(比如说堆、平衡树等),这样处理单个元素的复杂度提升为 \(logN\) ,就会出现 \(O(N\sqrt NlogN)\) 这种玄学复杂度。

具体怎么做?

莫队快速回答问题的基础是“上一次查询的答案”,于是先把每一个 \(A_i\) 的第一个询问 \(Q_j\) 暴力处理出来,得到一组答案(当然如果懒的话,只处理第一块的第一个询问也是 OK 的)。然后把这组答案经过左右端点暴力调整更新后,用来回答所属块内的其他询问。

静态莫队例题

T1 [国家集训队]小Z的袜子

最经典的莫队例题,也是莫队算法的出处。

题目链接:Link

题目描述:

给定一个长度为 \(n\) 的序列 \(A\) ,有 \(m\) 次询问,每次在 \([l,r]\) 内随机选两个数 \(A_i,A_j\) ,询问这两个数相同的概率。

Solution:

要求概率,先得把式子一推。

考虑在区间 \([l,r]\) 之间, 数 \(i\) 出现了 \(x_i\) 次,那么两抓都抓到 \(i\) 的概率很好算:

\[p=\frac{x_i}{r-l+1}\times \frac{x_i-1}{r-l}= \frac{x_i^2-x_i}{(r-l+1)\times(r-l)} \]

如果这段区间内一共有 \(c\) 种数,根据加法原理,总概率为:

\[p=\frac{\sum_cx_i^2-\sum_cx_i}{(r-l+1)\times (r-l)} \]

其中 \(\sum_cx_i\) 显然就是区间中所有的数之和,也就是 \(r-l+1\) ,于是式子中只有 \(\sum_c x_i^2\) 是变量,也就是我们需要维护的量。建立一个变量 \(ans\) 来维护这个值,那么整段的答案就可以由 \(ans\) 计算得到。

要想使用莫队,还得搞定单个元素对答案 \(ans\) 的影响:

  1. 添加一个元素对 \(ans\) 的影响:

    设这个元素在添加前在 \([l,r]\) 内共出现过 \(x\) 次,那么有:

    \[\Delta x=(x+1)^2-x^2=2x+1 \]

  2. 删除一个元素对 \(ans\) 的影响:

    设这个元素在删除前在 \([l,r]\) 内共出现过 \(x\) 次,那么有:

    \[\Delta x=(x-1)^2-x^2=-2x+1 \]

处理好单个元素影响后,就可以调整询问的左右端点,处理答案了。

Code:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>

//using namespace std;

const int maxn=50005;
#define int long long 

template <typename _T>
inline void read(_T &x){
  x=0;int fh=1;
  char ch=getchar();
  while(!isdigit(ch)){
    if(ch=='-')
      fh=-1;
    ch=getchar();
  }
  while(isdigit(ch)){
    x=(x<<3)+(x<<1)+ch-'0';
    ch=getchar();
  }
  x*=fh;
}

int gcd(const int x,const int y){
  if(!y) return x;
  return gcd(y,x%y);
}//题目要求输出最简分数

int n,m,len;
int A[maxn],bel[maxn];

struct Node{
  int l,r,org;//l,r表示左右端点,org表示这是第几个询问,用于处理答案
};
struct Node query[maxn];

inline bool operator < (const Node a,const Node b){
  return bel[a.l]!=bel[b.l]?bel[a.l]<bel[b.l]:a.r<b.r;
}//先按块分,再按右端点分

int num[maxn],ans;//num是桶,即i在当前区间出现了num[i]次

void add(const int i){
  ans+=num[i]*2;
  ans++;
  num[i]++;
}

void del(const int i){
  ans-=num[i]*2;
  ans++;
  num[i]--;
}//添加,删除单个元素影响
//根据上面推出的式子更新ans的值

int ans1[maxn],ans2[maxn];//这两个用来记录分子分母

signed main(){
  read(n),read(m);
  len=(int)std::sqrt(n);
  for(int i=1;i<=n;++i){
    bel[i]=(i-1)/len+1;//记第i个元素属于bel[i]块
    read(A[i]);
  }
  for(int i=1;i<=m;++i)
    read(query[i].l),read(query[i].r),query[i].org=i;
  std::sort(query+1,query+1+m);//读入所有询问后排序
  for(int i=query[1].l;i<=query[1].r;++i)
    add(A[i]);//暴力处理第一段答案
  ans1[query[1].org]=ans-(query[1].r-query[1].l+1);
  ans2[query[1].org]=(query[1].r-query[1].l+1)*(query[1].r-query[1].l);
  if(ans1[query[1].org]==0) 
    ans2[query[1].org]=1;
  else{
    int g=gcd(ans1[query[1].org],ans2[query[1].org]);
    ans1[query[1].org]/=g;
    ans2[query[1].org]/=g;
  }
  for(int i=2;i<=m;++i){//根据第一段的答案处理剩下的答案
    if(query[i-1].l<query[i].l)
      for(int j=query[i-1].l;j<query[i].l;++j)
        del(A[j]);
    else 
      for(int j=query[i].l;j<query[i-1].l;++j)
        add(A[j]);
    
    if(query[i-1].r<query[i].r)
      for(int j=query[i-1].r+1;j<=query[i].r;++j)
        add(A[j]);
    else 
      for(int j=query[i].r+1;j<=query[i-1].r;++j)
        del(A[j]);
	//这些都是为了调整块长
    ans1[query[i].org]=ans-(query[i].r-query[i].l+1);
    ans2[query[i].org]=(query[i].r-query[i].l+1)*(query[i].r-query[i].l);
    if(ans1[query[i].org]==0)//统计出这个询问的答案
      ans2[query[i].org]=1;
    else{
      int g=gcd(ans1[query[i].org],ans2[query[i].org]);
      ans1[query[i].org]/=g;
      ans2[query[i].org]/=g;
    }
  }
  for(int i=1;i<=m;++i)
    printf("%lld/%lld\n",ans1[i],ans2[i]);
  return 0;
}

T2 洛谷P3901 数列找不同

题目链接:Link

题目描述:

给定长度为 \(n\) 的序列 \(A(A_i\in [1,n])\),有 \(m\) 次询问,每次询问 \([l,r]\) 内元素是否各不相同。

Solution:

有点像上个例题,还是考虑开桶记录每个 \(A_i\) 的出现次数。同时还要维护一个 \(cnt\) 表示当前区间有多少个重复元素,每次更新桶内元素时顺便更新 \(cnt\) 。如果 \(cnt=0\) ,说明这段内元素各不相同,否则则出现重复。

Code:

主体框架和 T1 一样,故只给出 add 和 del 部分的代码。

void add(const int i){
  num[i]++;
  if(num[i]>1) cnt++;
  if(cnt>0) ans=0;
  else ans=1;
}

void del(const int i){
  num[i]--;
  if(num[i]>=1) cnt--;
  if(cnt==0) ans=1;
  else ans=0;
}

T3 [SDOI2009]HH的项链

这题在我之前的博客里讨论过主席树做法,现在看看莫队做法。

题目链接:Link

题目描述:

给定一个长度为 \(n\) 的序列 \(A(A_i\in [1,1e6])\),有 \(m\) 次询问,每次询问 \([l,r]\) 之间有多少个互不相同的元素。

Solution:

这题用主席树还要想想,起码要想到预处理 \(A_i\) 下一次什么时候出现,然后才能用主席树维护。但是如果用莫队...

这不是 shabi 题吗?

还是开桶,直接用 \(ans\) 维护不同元素的数量,回答每个询问。

Code:

和 T1 基本一样,故仍只给出 add 和 del 的代码。

因为这题出题人有意在卡莫队,所以莫队只能拿 72 分(当年用主席树也没放我过啊)

另外,静态莫队还有一个小优化:奇偶性优化。即编号是奇数的块按 \(r_j\) 从小到大,否则从大到小排序。

inline bool operator < (const Node a,const Node b){
  return bel[a.l]!=bel[b.l]?bel[a.l]<bel[b.l]:a.r<b.r;
}//奇偶性优化

inline void add(const int i){
  num[i]++;
  if(num[i]==1) ans++;
}

inline void del(const int i){
  num[i]--;
  if(num[i]==0) ans--;
}
这篇关于静态莫队分块的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!