关于时间复杂度

对于多维莫队的复杂度差不多为\(O(n^{\frac{2k-1}{k}})\)

奇偶分类优化

return a.l == b.l ? (a.l & 1) ? a.r
    
     b.r  :  a.l < b.l;
    

貌似不会用会变慢的好多，谨慎的用

思路

好久的题目了，之前其实只会点不修改莫队

对带修改的不大会，也就做过这一个题目

今天重新做了一边，算是有了新的认识了

其实是在不修改的莫对上加了一个时间戳

修改时的时候和时间一起移动就好了

虽然复杂度会更高(所以一般莫队待修改就很慢了)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define FOR(i,a,b) for(int i=a;i<=b;++i)using namespace std;const int maxn=5e4+7;const int maxm=1e6+7;char s;int n,m,A,B,a[maxn],belong[maxn],vis[maxm],ans;struct node {    int x,y,id,tim,ans;}Q[maxn];struct modify {    int id,v;}C[maxn];bool cmp1(const node &a,const node &b) {    return belong[a.x]==belong[b.x] ? (belong[a.y]==belong[b.y] ? a.tim
         
          '9';s=getchar()) if(s=='-') f=-1; for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0'; return x*f;}void add(int x) { if(!vis[a[x]]) ++ans; ++vis[a[x]];}void delet(int x) { --vis[a[x]]; if(!vis[a[x]]) --ans;}void work(int x,int i){ if(Q[i].x<=C[x].id && C[x].id<=Q[i].y) { --vis[a[C[x].id]]; ++vis[C[x].v]; if(!vis[a[C[x].id]]) --ans; if(vis[C[x].v]==1) ++ans; } swap(C[x].v,a[C[x].id]);}int main() { n=read(),m=read(); int k=sqrt(n)*7; FOR(i,1,n) a[i]=read(); FOR(i,1,n) belong[i]=(i-1)/k+1; FOR(i,1,m) { scanf("%s",&s); if(s=='Q') { Q[++A].id=A; Q[A].tim=B; Q[A].x=read(); Q[A].y=read(); } else { C[++B].id=read(); C[B].v=read(); } } sort(Q+1,Q+1+A,cmp1); int l=1,r=0,ttt=0; FOR(i,1,A) { while(Q[i].x
          
           l) delet(l++); while(Q[i].y>r) add(++r); while(Q[i].y
           
            ttt) work(++ttt,i); while(Q[i].tim