题解 P3901 【数列找不同】
莫队算法
（Mo's Algorithm）众所周知，这是一种
玄学的暴力骗分区间操作算法普通莫队是一种离线算法，要处理更高端的问题我们还需要带修莫队/树上莫队等等，这里先不谈
前置知识：分块，
不会的可以上b站康康
先看本题：
已知一个序列，给出Q次询问，每次询问区间[L，R]所有数是否互不相同，如果是输出“Yes”，否则输出“No”。
很简单的暴力思路就是找出区间[L，R]所有互不相同的数的个数k，接着判断k是否等于R-L+1即可，接下来就是莫队裸题了。
莫队的处理方法：
举个例子：如图，对于这样一个序列，我们已知一个询问：q[i].l=3，q[i].r=7，我们想知道区间[3,7]内有多少个不同的数。
不妨先定义一个L=1，R=0，Ans=0
接下来我们只需要扫一遍：
inline void add(int x){
cnt[x]++;
if(cnt[x]==1) Ans++;
}
inline void del(int x){
cnt[x]--;
if(cnt[x]==0) Ans--;
}
对于每个询问：
while(L<q[i].l) del(a[L++]);
while(L>q[i].l) add(a[--L]);
while(R<q[i].r) add(a[++R]);
while(R>q[i].r) del(a[R--]);
ans[q[i].id]=Ans;
如果L小于所询问的q[i].l的话，L自然需要右移：
这个时候，旧L对Ans的影响就需要被删去，即：
del(a[L++])而del函数的实现也很容易理解： cnt[x]表示的是数字x出现的次数，那么cnt[x]--即可
如果cnt[x]等于0的话，就说明目前的[L，R]中已经没有x这个数了，那么Ans--
其它几个和这个是同样的道理，理解了这里就很简单了，处理结束后在ans数组中记录Ans即可。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int M=1e6;
struct node{
int l,r,id;
int ll,rr;
}q[M];
int a[M],cnt[M],n,m,pos[M],ans[M],L=1,R=0,Ans=0,block;
bool cmp(const node &x,const node &y){
if(pos[x.l]==pos[y.l]) return x.r>y.r;
return pos[x.l]<pos[y.l];
}
//cmp函数用于排序，不难得知，用这样的方法排序之后算法的扫描次数会大幅降低，时间复杂度也能相应降低
inline void add(int x){
cnt[x]++;
if(cnt[x]==1) Ans++;
}
inline void del(int x){
cnt[x]--;
if(cnt[x]==0) Ans--;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
block=sqrt(n);
for(register int i=1;i<=n;i++){
cin>>a[i];
pos[i]=i/block;//分块
}
for(register int i=1;i<=m;i++){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
for(register int i=1;i<=m;i++){
while(L<q[i].l) del(a[L++]);
while(L>q[i].l) add(a[--L]);
while(R<q[i].r) add(a[++R]);
while(R>q[i].r) del(a[R--]);
ans[q[i].id]=Ans;
q[q[i].id].ll=q[i].l;//得出答案后不要忘记将对应的q[i].l/r存储以便后续比较
q[q[i].id].rr=q[i].r;
}
for(register int i=1;i<=m;i++){
if(ans[i]==q[i].rr-q[i].ll+1) cout<<"Yes"<<endl;//如果Ans=R-L+1那么输出Yes，否则输出No
else cout<<"No"<<endl;
}
return 0;
}