分块大法好 orz

处理出每个点的前驱和后继位置。

暴力修改，查询就在每个整块里查询pre<l的，暴力跑两边就好了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define N 10005using namespace std;int n,m,nn,a[N],be[N],pre[N],nxt[N];int last[1000005],pp[N],ans;void work(int x){	int l=(x-1)*nn+1,r=min(n,x*nn);	for(int i=l;i<=r;i++)		pp[i]=pre[i];	sort(pp+l,pp+r+1);}void change(int x,int y){	a[x]=y;	if(nxt[x]){pre[nxt[x]]=pre[x];work(be[nxt[x]]);}	if(pre[x]){nxt[pre[x]]=nxt[x];work(be[pre[x]]);}	int pr=0,ne=0;	for(int i=1;i<=n;i++){		if(i
         
          x&&a[i]==y){ne=i;break;} } pre[x]=pr; nxt[x]=ne; work(be[x]); if(pr) {nxt[pr]=x;work(be[pr]);} if(ne) {pre[ne]=x;work(be[ne]);}}int main(){ scanf("%d%d",&n,&m); nn=(int) sqrt(n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); be[i]=(i-1)/nn+1; } for(int i=1;i<=n;i++){ pre[i]=last[a[i]]; last[a[i]]=i; if(pre[i]) nxt[pre[i]]=i; } int tot=be[n]; for(int i=1;i<=tot;i++)work(i); char ch; int x,y,l,r,num; while(m--){ ch=getchar(); while(ch!='Q'&&ch!='R')ch=getchar(); scanf("%d%d",&x,&y); if(ch=='Q'){ ans=0; if(be[x]==be[y]){ for(int i=x;i<=y;i++)if(pre[i]