P3901 数列找不同(莫队)

P3901 数列找不同(莫队）

思路：询问转离线排序普通莫队。

时间复杂度：$O(n\sqrt{n})$O(nn​)

貌似树状数组或者主席树都能做。。
第一次写板子把代码注释的详细一下。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
template<class T>
inline void read(T &x){ 
	x=0;int w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<3)+(x<<1)+(ch&15);
	x*=w; 
}
int n,Q,a[N],block,tot,cnt[N];	//cnt[i]表示颜色i当前的次数，tot表示当前颜色种类数. 
int ans[N];
struct query{
	int l,r,id,bk;//id表示原来询问的编号,bk表示属于那个块. 
}q[N];
bool cmp(query a,query b){	//按照奇偶性排序,貌似玄学优化. 
	return a.bk!=b.bk?a.l<b.l:((a.bk&1)?a.r<b.r:a.r>b.r);
}
il void add(int x)
{
	if(++cnt[a[x]]==1)
		++tot; 
}
il void del(int x)
{
	if(--cnt[a[x]]==0)
		--tot;
}
int main(){
	/*
	freopen("input.in","r",stdin);
	freopen("output.txt","w",stdout);
	*/
	read(n);
	block=sqrt(n);//分块大小. 
	for(reg int i=1;i<=n;i++) read(a[i]);
	read(Q);
	for(reg int i=1;i<=Q;i++){
		 int l,r;
		 read(l),read(r);
		q[i]={l,r,i,(l-1)/block+1};
	} 
	sort(q+1,q+Q+1,cmp);
	int L=1,R=0;
	for(reg int i=1;i<=Q;i++){
		int l=q[i].l,r=q[i].r;
		while(L<l) del(L++);
		while(L>l) add(--L);
		while(R<r) add(++R);
		while(R>r) del(R--); 
		ans[q[i].id]=tot;
	}
	for(reg int i=1;i<=Q;i++)
		printf("%d\n",ans[i]);
}

顺便附上普通的排序（貌似已经被淘汰了）

bool cmp(query a,query b){
	return a.bk==b.bk?a.r<b.r:a.bk<b.bk;
}