分块，对于每一块，按照“之前第一个与i颜色相同的位置” 排序，在块内二分即可

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #define re(i,l,r) for(int i=(l);i<=(r);i++) 9 using namespace std;10 template 
            
             11 void inin(Q &ret)12 {13 ret=0;int f=0;char ch=getchar();14 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();}15 while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();16 ret=f?-ret:ret;17 }18 int n,q,block,m,a[10010],shang[1000010],sorted[10010],wei[10010],sorting[10010];19 int query2(int x,int l)20 {21 int L=x*block-block+1,R=x*block;R=min(R,n);22 int mid,ret=L-1,ll=L;23 while(L<=R)24 {25 mid=(L+R)>>1;26 if(sorted[mid]