题目大意：给定一个序列。求一个区间内有多少个不同的数

正解是树状数组 将全部区间依照左端点排序 然后每次仅仅统计左端点開始的每种颜色的第一个数即可了 用树状数组维护

我写的是莫队算法 莫队明显能搞 m√m明显慢了点可是还是能接受的一个复杂度

一開始离散化数组开小了各种秒RE…… 跪了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define M 50500using namespace std;struct abcd{	int l,r,pos;	bool operator < (const abcd &x) const;}q[200200];int n,m,block,l=1,r=0,now,a[M],map[1001001],tot;int cnt[M],ans[200200];bool abcd :: operator < (const abcd &x) const{	if( (l-1)/block == (x.l-1)/block )		return r < x.r ;	return (l-1)/block < (x.l-1)/block ;}inline void Update(int x){	cnt[x]++;	if(cnt[x]==1)		++now;}inline void Downdate(int x){	cnt[x]--;	if( !cnt[x] )		--now;}int main(){	int i,x;	cin>>n;	for(i=1;i<=n;i++)	{		scanf("%d",&x);		if(!map[x]) map[x]=++tot;		a[i]=map[x];	}	cin>>m;	for(i=1;i<=m;i++)		scanf("%d%d",&q[i].l,&q[i].r),q[i].pos=i;	block=static_cast
          
           (sqrt(n)+1e-7); sort(q+1,q+m+1); for(i=1;i<=m;i++) { while(r
           
            q[i].l) Update(a[--l]); while(r>q[i].r) Downdate(a[r--]); while(l