本文共 3294 字，大约阅读时间需要 10 分钟。
分块
我们把数列分成$\sqrt{N}$块
记$f[i][j]$表示第i块到第j块的答案，这个可以在$O(N\sqrt{N})$内得到。
记$g[i][j]$第1到第i块中数字j出现了多少次，这个我们可以先求出第i块中数字j出现了多少次，然后求前缀和即可，这个可以在$O(C\sqrt{N})$内得到。
对于询问区间[l,r]我们可以从f数组中快速求出中间连续的完整的块答案。
对于剩余部分，我们可以一个一个调整答案，反正剩余部分的长度是$\sqrt{N}$级别的。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include 适用于CF,UOJ，但不适用于pojusing namespace std;typedef long long LL;typedef double DB;typedef pair PII;typedef complex CP;#define mmst(a,v) memset(a,v,sizeof(a))#define mmcy(a,b) memcpy(a,b,sizeof(a))#define fill(a,l,r,v) fill(a+l,a+r+1,v)#define re(i,a,b) for(i=(a);i<=(b);i++)#define red(i,a,b) for(i=(a);i>=(b);i--)#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)#define fi first#define se second#define m_p(a,b) make_pair(a,b)#define p_b(a) push_back(a)#define SF scanf#define PF printf#define two(k) (1<<(k))template inline T sqr(T x){ return x*x;}template inline void upmin(T &t,T tmp){ if(t>tmp)t=tmp;}template inline void upmax(T &t,T tmp){ if(t 0)?1:-1;}const DB Pi=acos(-1.0);inline int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; }inline LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; }const int maxN=100000;const int maxC=100000;const int maxcnt=320;int N,C,Q;int a[maxN+10];int cnt,len,l[maxcnt+10],r[maxcnt+10];int id[maxN+100];int f[maxcnt+3][maxcnt+3];int g[maxcnt+3][maxC+3];int t[maxC+10];int ans;int main() { freopen("bzoj2821.in","r",stdin); freopen("bzoj2821.out","w",stdout); int i,j,k; N=gint();C=gint();Q=gint(); re(i,1,N)a[i]=gint(); len=int(sqrt(DB(N))); re(i,1,N) { if((i-1)%len==0)r[cnt]=i-1,l[++cnt]=i; id[i]=cnt; } r[cnt]=N; re(i,1,cnt) { int res=0; re(j,i,cnt) { re(k,l[j],r[j]) { t[a[k]]++; if(t[a[k]]>=2 && !(t[a[k]]&1))res++; if(t[a[k]]>=3 && (t[a[k]]&1))res--; } f[i][j]=res; } re(k,l[i],N)t[a[k]]--; } re(i,1,cnt)re(j,l[i],r[i])g[i][a[j]]++; re(i,2,cnt)re(j,1,C)g[i][j]+=g[i-1][j]; ans=0; while(Q--) { int L=(gint()+ans)%N+1,R=(gint()+ans)%N+1,res=0; if(L>R)swap(L,R); if(id[L]==id[R] || id[L]+1==id[R]) { re(i,L,R) { t[a[i]]++; if(t[a[i]]>=2 && !(t[a[i]]&1))res++; if(t[a[i]]>=3 && (t[a[i]]&1))res--; } re(i,L,R)t[a[i]]--; ans=res; } else { int p=(L==l[id[L]])?id[L]:id[L]+1,q=(R==r[id[R]])?id[R]:id[R]-1; res=f[p][q]; red(i,l[p]-1,L) { t[a[i]]++; t[a[i]]+=g[q][a[i]]-g[p-1][a[i]]; if(t[a[i]]>=2 && !(t[a[i]]&1))res++; if(t[a[i]]>=3 && (t[a[i]]&1))res--; t[a[i]]-=g[q][a[i]]-g[p-1][a[i]]; } re(i,r[q]+1,R) { t[a[i]]++; t[a[i]]+=g[q][a[i]]-g[p-1][a[i]]; if(t[a[i]]>=2 && !(t[a[i]]&1))res++; if(t[a[i]]>=3 && (t[a[i]]&1))res--; t[a[i]]-=g[q][a[i]]-g[p-1][a[i]]; } red(i,l[p]-1,L)t[a[i]]--; re(i,r[q]+1,R)t[a[i]]--; ans=res; } PF("%d\n",ans); } return 0; }
转载于:https://www.cnblogs.com/maijing/p/4768725.html
