https://blog.csdn.net/niiick/java/article/details/80327593
就是用一个cnt[]数组记录当前每个数字出现了多少次
然后用左L，右R指针不断移动来获得当前区间的cnt[]数组
增加时每当有一个cnt[i]==1就代表新增加了一个数字
删除时每当有一个cnt[i]==0就代表新减少了一个数字
但是既然都说了这是一个暴力，这样当然是过不了
不过这就是莫队算法的其中一个核心了
考虑到这样做会T的原因是左右指针移动次数无法确定‘
所以我们可以改变对询问的处理顺序，采用离线算法
具体怎么改变询问顺序呢
我们将整个序列按分块思想分成sqrt（N）块，每块有sqrt（N）个元素
然后将询问排序，具体方法是
以询问左区间L所在块为第一关键字
询问右区间R为第二关键字排序
现在所有询问左区间所在块是单调递增的
所以左指针移动次数不超过M*sqrt（N）次
由于同一个块内所有询问右指针单调递增
一个块内的询问右指针移动最大为N， NN,总共sqrt（N）个块
所以右指针移动次数不超过N*?sqrt（N）次
整体复杂度O((N+M) *sqrt（N）
模板题：BZOJ1878 [SDOI2009]HH的项链
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int read()
{
int f=1,x=0;
char ss=getchar();
while(ss<‘0‘||ss>‘9‘){if(ss==‘-‘)f=-1;ss=getchar();}
while(ss>=‘0‘&&ss<=‘9‘){x=x*10+ss-‘0‘;ss=getchar();}
return x*f;
}
int t,n,m;
int L=1,R=0,a[500010];
int cnt[1000010];
struct node{int ll,rr,num;}q[200010];
bool cmp(node a,node b){return (a.ll/t)==(b.ll/t) ?a.rr<b.rr :(a.ll/t)<(b.ll/t);}
int ans[200010],sum;
void add(int x)
{
cnt[x]++;
if(cnt[x]==1) sum++;
}
void del(int x)
{
cnt[x]--;
if(cnt[x]==0) sum--;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
m=read();
for(int i=1;i<=m;++i)
q[i].ll=read(),q[i].rr=read(),q[i].num=i;
t=sqrt(n);//块数
sort(q+1,q+1+m,cmp);
for(int i=1;i<=m;++i)
{
while(R<q[i].rr) add(a[++R]);
while(R>q[i].rr) del(a[R--]);
while(L<q[i].ll) del(a[L++]);
while(L>q[i].ll) add(a[--L]);
ans[q[i].num]=sum;
}
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}
带修改的莫队
同样先看问题
Q：有一个长为N序列，有M个操作：
查询操作，查询在区间[L,R]内，出现了多少个不同的数字。
修改操作，修改第x个数字为y
(数字范围为0到1000000之间的整数)，N ≤ 50000，M ≤ 50000。
带上了修改的思路依旧很暴力
对于每个询问记录在这个询问前修改了多少次
改多了或改少了都一个while改回来
不过这里分块要变成
每块大小N^(2/3) ，总共N^(1/3)块
且要加入修改顺序为第三关键字排序
这样左右指针，修改指针移动次数都是N∗N^(3/2)
所以整个算法渐进复杂度O(N^(5/3)
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int read()
{
int f=1,x=0;
char ss=getchar();
while(ss<‘0‘||ss>‘9‘){if(ss==‘-‘)f=-1;ss=getchar();}
while(ss>=‘0‘&&ss<=‘9‘){x=x*10+ss-‘0‘;ss=getchar();}
return x*f;
}
const int maxn=50010;
int n,m,t;
int a[maxn],cnt[2000010];
int cntq,cntc;
int L=1,R=0,cur,sum;
struct node{int ll,rr,num,id,pre;}q[maxn];
struct node2{int pos,val;}c[maxn];
int ans[maxn];
bool cmp(node a,node b)
{
if(a.ll/t!=b.ll/t) return a.ll/t<b.ll/t;//左端点按块
if(a.rr/t!=b.rr/t)
{
if((a.ll/t)&1) return a.rr<b.rr;//右端点奇偶块排序优化
else return a.rr>b.rr;
}
return a.pre<b.pre;//修改顺序排
}
void add(int x)
{
cnt[x]++;
if(cnt[x]==1) sum++;
}
void del(int x)
{
cnt[x]--;
if(cnt[x]==0) sum--;
}
void update(int cur)
{
if(c[cur].pos>=L&&c[cur].pos<=R)//修改在当前查询区间里才要更新
{
if(--cnt[ a[ c[cur].pos ] ]==0) sum--;
if(++cnt[ c[cur].val ]==1) sum++;
}
swap(c[cur].val,a[c[cur].pos]);//因为可能多次更改，所以直接交换要改的数
}
int main()
{
n=read();m=read(); t=pow(n,2.0/3);//**高亮**，注意分块大小
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=m;++i)
{
char ss; scanf("%s",&ss);
if(ss==‘Q‘)
{
q[++cntq].ll=read(); q[cntq].rr=read();
q[cntq].pre=cntc; //记录上一次修改编号
q[cntq].num=cntq;
}
else if(ss==‘R‘)
c[++cntc].pos=read(),c[cntc].val=read();//记录修改
}
sort(q+1,q+1+cntq,cmp);
for(int i=1;i<=cntq;++i)
{
while(R<q[i].rr) add(a[++R]);
while(R>q[i].rr) del(a[R--]);
while(L<q[i].ll) del(a[L++]);
while(L>q[i].ll) add(a[--L]);
while(cur<q[i].pre) update(++cur);//把改多/少的改回来
while(cur>q[i].pre) update(cur--);
ans[q[i].num]=sum;
}
for(int i=1;i<=cntq;++i)
printf("%d\n",ans[i]);
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/12861029.html