处理单次询问时间复杂度为n1/2，可以通过本题 。
#include<bits/stdc++.h>using namespace std;const int h=100010;const int b_h=1010;int n,m,c;int len;int a[h];int sum[b_h][b_h];int tim[b_h][h];int tmp[h];int get_pos(int x){ return (x-1)/len+1;}void get_pre(){ for(int i=1;i<=get_pos(n);i++) for(int j=1;j<=c;j++) tim[i][j]+=tim[i-1][j]; for(int i=1;i<=get_pos(n);i++){ int kin=0; for(int j=i;j<=get_pos(n);j++){ for(int k=(j-1)*len+1;k<=min(n,j*len);k++){ tmp[a[k]]++; if((tmp[a[k]]&1)) if(tmp[a[k]]>1) kin--; else kin+=0; else kin++; } sum[i][j]=kin; } for(int j=1;j<=c;j++) tmp[j]=0; }}int l,r,lb,rb;int ans;void get_vio(){ ans=0; for(int i=l;i<=r;i++){ tmp[a[i]]++; if((tmp[a[i]]&1)) if(tmp[a[i]]>1) ans--; else ans+=0; else ans++; } for(int i=l;i<=r;i++) tmp[a[i]]--;}void get_q(){ ans=0; for(int i=l;i<=lb*len;i++){ tmp[a[i]]++; if(tmp[a[i]]&1) if((tim[rb-1][a[i]]-tim[lb][a[i]])&1) ans++; else if(tim[rb-1][a[i]]-tim[lb][a[i]]>0) ans--; else if(tmp[a[i]]>1) ans--; else ans-=0; else if(tim[rb-1][a[i]]-tim[lb][a[i]]&1) ans--; else ans++; } for(int i=(rb-1)*len+1;i<=r;i++){ tmp[a[i]]++; if(tmp[a[i]]&1) if((tim[rb-1][a[i]]-tim[lb][a[i]])&1) ans++; else if(tim[rb-1][a[i]]-tim[lb][a[i]]>0) ans--; else if(tmp[a[i]]>1) ans--; else ans-=0; else if(tim[rb-1][a[i]]-tim[lb][a[i]]&1) ans--; else ans++; } for(int i=l;i<=lb*len;i++) tmp[a[i]]--; for(int i=(rb-1)*len+1;i<=r;i++) tmp[a[i]]--; ans+=sum[lb+1][rb-1];}int main(){ scanf("%d%d%d",&n,&c,&m); len=sqrt(n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),tim[get_pos(i)][a[i]]++; get_pre(); int lst=0; for(int i=1;i<=m;i++){ scanf("%d%d",&l,&r); l=(l+lst)%n+1,r=(r+lst)%n+1; if(l>r) swap(l,r); lb=get_pos(l),rb=get_pos(r); if(lb>=rb-1) get_vio(); else get_q(); lst=ans; printf("%d\n",ans); } return 0;}
经验总结扩展阅读
- 带权bitset?/bitset优化莫队 模板 洛谷P4135 Ynoi2016 掉进兔子洞 题解
- 洛谷P5309 Ynoi 2011 初始化 题解
- 洛P8109题解
- 自是指物作诗立就是什么意思 自是指物作诗立就的意思是什么
- 好听的微信名字诗意