题解：

每个数第一次出现时随便改成pos-n，之后改成前一次出现的位置。询问的时候查找一个区间中比左端点小的数的个数

 

吐槽：

尼玛数组越界了查了一晚上+半个下午。

树套树这种东西真难查错！

我多插入了很多没有用的节点，所以就慢了点，不过省代码~

 

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6    7 #define N 6000050  8 #define INF 520131499  9 #define CN 1000000 10 #define lowbit(x) x&-x 11 #define BUG system("pause"); 12 #define CA puts("ca"); 13   14 using namespace std; 15   16 int sz[N],val[N],fa[N],son[N][2]; 17 int rc[CN+10],root[N],col[N]; 18 int cnt,num,q[N+CN]; 19 int suf[N],pre[N],jp[CN+10]; 20 int n,m; 21  22 inline void prt(int x) 23 { 24     if(!x) return; 25     prt(son[x][0]); 26     printf("%d    ",val[x]); 27     prt(son[x][1]); 28 } 29  30 inline void pushup(int x) 31 { 32     if(!x) return; 33     sz[x]=sz[son[x][0]]+sz[son[x][1]]+1; 34 } 35   36 inline void link(int x,int y,int c) 37 { 38     fa[x]=y; son[y][c]=x; 39 } 40   41 inline void rotate(int x,int c) 42 { 43     int y=fa[x]; 44     link(x,fa[y],son[fa[y]][1]==y); 45     link(son[x][!c],y,c); 46     link(y,x,!c); 47     pushup(y); 48 } 49   50 inline void splay(int x,int g,int &rt) 51 { 52     while(fa[x]!=g) 53     { 54         int y=fa[x]; 55         int cy=(son[fa[y]][1]==y),cx=(son[y][1]==x); 56         if(fa[y]==g) rotate(x,cx); 57         else 58         { 59             if(cx==cy) rotate(y,cy); 60             else rotate(x,cx); 61             rotate(x,cy); 62         } 63     } 64     pushup(x); 65     if(!g) rt=x; 66 } 67   68 inline int getnum() 69 { 70     if(num==0) return ++cnt; 71     return q[num--]; 72 } 73   74 inline void newnode(int y,int &x,int sp) 75 { 76     x=getnum(); 77     fa[x]=y; val[x]=sp; sz[x]=1; 78     son[x][1]=son[x][0]=0; 79 } 80   81 inline int getmin(int x) 82 { 83     while(son[x][0]) x=son[x][0]; 84     return x; 85 } 86   87 inline int getmax(int x) 88 { 89     while(son[x][1]) x=son[x][1]; 90     return x; 91 } 92   93 inline int pred(int x,int sp) 94 { 95     int res=-INF-10,ans=x; 96     while(x) 97     { 98         if(val[x]==sp) return x; 99         else if(val[x]
           
            res) res=val[x],ans=x;100 x=son[x][val[x]
            
             sp&&val[x]
             
              n) suf[pre[x]]=pre[x]+n;164 }165 del(rc[col[x]],x); insert(rc[y],x);//颜色splay中删除旧颜色，添加新颜色 166 int l=val[getmax(son[rc[y]][0])],r=val[getmin(son[rc[y]][1])];//新颜色的前缀和后缀（新） 167 if(l!=-INF) pre[x]=l,suf[l]=x;//前缀和当前建立关系 （新） 168 else pre[x]=x-n; 169 if(r!=INF)//存在后缀 （新） 170 {171 for(int i=r;i<=n;i+=lowbit(i)) del(root[i],pre[r]);//删除新颜色的后缀的前缀 （新） 172 suf[x]=r;pre[r]=x;//后缀和当前建立关系 173 for(int i=r;i<=n;i+=lowbit(i)) insert(root[i],pre[r]);//插入新颜色的前缀 （新） 174 }175 else suf[x]=n+x;176 for(int i=x;i<=n;i+=lowbit(i)) insert(root[i],pre[x]);//插入当前颜色的前缀 （新） 177 col[x]=y;178 }179 180 inline void read()181 {182 scanf("%d%d",&n,&m);183 for(int i=1;i<=n;i++)184 {185 scanf("%d",&col[i]);186 newnode(0,root[i],-INF);187 newnode(root[i],son[root[i]][1],INF);188 sz[root[i]]=2;189 }190 for(int i=1;i<=n;i++)191 {192 if(!jp[col[i]]) pre[i]=i-n;193 else pre[i]=jp[col[i]];194 jp[col[i]]=i;195 }196 for(int i=1;i<=CN;i++) jp[i]=n+1;197 for(int i=n;i>=1;i--)198 {199 if(jp[col[i]]==n+1) suf[i]=i+n;200 else suf[i]=jp[col[i]];201 jp[col[i]]=i;202 }203 for(int i=1;i<=CN;i++)204 {205 newnode(0,rc[i],-INF);206 newnode(rc[i],son[rc[i]][1],INF);207 sz[rc[i]]=2;208 }209 }210 211 inline void go()212 {213 for(int i=1;i<=n;i++)214 {215 for(int j=i;j<=n;j+=lowbit(j)) insert(root[j],pre[i]);216 insert(rc[col[i]],i);217 }218 char str[3];int x,y;219 while(m--)220 {221 scanf("%s%d%d",str,&x,&y);222 if(str[0]=='Q') printf("%d\n",getans(y,x)-getans(x-1,x));223 else updata(x,y);224 }225 }226 227 int main()228 {229 read(),go();230 return 0;231 }
             
            
           
          
         
        
       
      

 

 赠送对拍器：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 int main()10 {11     srand(time(0));12     while(1)13     {14         FILE *fp=fopen("3.txt","w");15         int n=10,m=20;16         fprintf(fp,"%d %d\n",n,m);17         for(int i=1;i<=n;i++) fprintf(fp,"%d ",rand()%6+1);18         fprintf(fp,"\n");19         for(int i=1;i<=m;i++)20         {21             int a,b,c;22             a=rand()&1;23             b=rand()%10+1;24             if(a)25             {26                 c=rand()%10+1;27                 if(b>c) swap(b,c);28                 fprintf(fp,"Q %d %d\n",b,c);29             }30             else31             {32                 c=rand()%6+1;33                 fprintf(fp,"R %d %d\n",b,c);34             }35         }36         fclose(fp);37         system("1.exe");system("2.exe");38         if(system("fc 1.txt 2.txt"))39         {40             puts("ca");41             getchar();42         }43     }44     return 0;45 }