莫队
介绍
-
利用分块进行处理的离线算法；
-
时间复杂度普遍为 \(O(n\sqrt{n})\) ；
但会被卡
实现思路
对答案的查询
-
在已知区间的情况下暴力寻找的目标区间的贡献；
-
对于已知当前 \([L,R]\) 区间，一共有 \(4\) 种情况：
-
加上当前区间左边一格的贡献：
Add(--L);先将当前的下标移至目标格，然后加上当前格的贡献
-
加上当前区间右边一格的贡献：
Add(++R);同理
-
减去当前区间最左一格的贡献：
Sub(L++);先减去当前下标的贡献，然后将下标移至目标格
-
减去当前区间最右一格的贡献：
Sub(R--);同理
-
-
对于需要用到的函数 \(Add\) 和 \(Sub\) 分别为：
- \(Add(x)\) ：按照需求算上第 \(x\) 个元素的贡献；
- \(Sub(x)\) ：按照需求去除第 \(x\) 个元素的贡献；
分块的优化
如果仅仅只按上面的思路进行对答案的查询，当多次询问依次为：
\([1,2],[n-1,n],[1,2],[n-1,n]...\) 时，复杂度便成了 \(O(mn)\) ...
因此，我们需要优化对询问的查询顺序（这就是离线的原因）
-
将整体的区间分块，块大小为 \(\sqrt{n}\) ，然后再对询问进行排序，进行查找；
-
对查询操作排序时：
- 对于左端点 \(L\) 不在同一块的查询，按照 \(L\) 所在块进行排序；
- 对于左端点 \(L\) 在同一块的查询，按照 \(R\) 的大小排序；
-
在排序时保留询问的标号，最后按原顺序输出答案；
代码实现
\(Add\) 和 \(Sub\) 函数的实现需要具体按题目要求来。
定义分块
-
在输入元素时，需要对元素进行分块：
int n=read(); //输入元素的个数n int siz=sqrt(n);//计算块的大小 for(int i=1;i<=n;i++){ a[i]=read();//输入n个元素 pos[i]=i/siz;//计算第i个元素所属的块 并储存在pos[i]里 }在这里的分块会在后面对询问的排序中用到；
处理查询
-
定义结构体：
struct Q{ int l,r,k; bool operator<(Q x)const{ //处理规则如上 if(pos[l]==pos[x.l]) return r<x.r; return pos[l]<pos[x.l]; } }q[N]; /* 当然，也可以去掉bool operator一句 用手打排序函数来代替，例如： bool cmp(Q x,Q y){ if(pos[x.l]==pos[y.l]) return x.r<y.r; return pos[x.l]<pos[y.l]; } 在主函数中的sort加上“cmp”函数即可 */ -
进行处理：
for(int i=1;i<=m;i++){ //处理区间为[l,r]的查询，询问编号为k q[i].l=read(),q[i].r=read(); q[i].k=i; } sort(q+1,q+m+1);
查找答案
-
int l=1,r=0; /* 由于处理的是[l,r]的闭区间 因此空集应表示为l=r+1; 不然集合中会存在一个元素 例如： l=1,r=1时 集合为[1,1]，存在a[1]这个元素 */ for(int i=1;i<=m;i++){ //处理情况如上 while(q[i].l<l)Add(--l); while(q[i].r>r)Add(++r); while(q[i].l>l)Sub(l++); while(q[i].r<r)Sub(r--); //由于实际查询的顺序与输入输出不符 //因此需要改变输出顺序 ans[q[i].k]=res; }
例题
P2709 小B的询问
luogu传送门：题目链接
-
代码：
#include<algorithm> #include<iostream> #include<string.h> #include<stdio.h> #include<string> #include<vector> #include<math.h> #include<stack> #include<queue> #include<set> #include<map> using namespace std; int read(){ int s=0,f=1; char _z=getchar(); while(_z<'0'||_z>'9'){ if(_z=='-') f=-1; _z=getchar(); } while(_z>='0'&&_z<='9'){ s=(s<<3)+(s<<1)+(_z-'0'); _z=getchar(); } return s*f; } const int N=5e4+10; typedef long long ll; int a[N],pos[N],tot[N]; ll res=0,ans[N]; struct Q{ int l,r,k; bool operator<(Q x){ if(pos[l]==pos[x.l]) return r<x.r; return pos[l]<pos[x.l]; } }q[N]; void Add(int x){ x=a[x]; res-=tot[x]*tot[x]; tot[x]++; res+=tot[x]*tot[x]; return; } void Sub(int x){ x=a[x]; res-=tot[x]*tot[x]; tot[x]--; res+=tot[x]*tot[x]; return; } int main(){ int n=read(),m=read(); read(); int siz=sqrt(n); for(int i=1;i<=n;i++){ a[i]=read(); pos[i]=i/siz; } for(int i=1;i<=m;i++){ q[i].l=read(),q[i].r=read(); q[i].k=i; } sort(q+1,q+m+1); int l=1,r=0; for(int i=1;i<=m;i++){ while(q[i].l<l)Add(--l); while(q[i].r>r)Add(++r); while(q[i].l>l)Sub(l++); while(q[i].r<r)Sub(r--); ans[q[i].k]=res; } for(int i=1;i<=m;i++){ printf("%lld\n",ans[i]); } return 0; }