$O(N\sqrt(N))$做法
预处理出每一块到结尾每一种颜色的个数,以及块与块之间的答案。
每一次询问仅需$\sqrt(N)$的时间暴力拓展就好了。
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=1e5+10;
const int B=350;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
int l[B],r[B],cnt[320][N],f[B][B],a[N],pos[N],c[N],sta[N],top;bool v[N];
int main()
{
//freopen("a.in","r",stdin);
//freopen("a.ans","w",stdout);
int n,C,m;qr(n),qr(C),qr(m);
for(int i=1;i<=n;i++)qr(a[i]);
int bl=sqrt(n),sz=bl;
for(int i=1;i<=sz;i++)
{
l[i]=r[i-1]+1,r[i]=i*bl;
for(int j=l[i];j<=r[i];j++)
pos[j]=i;
}
if(r[sz]<n){l[sz+1]=r[sz]+1,r[++sz]=n;for(int i=l[sz];i<=r[sz];i++)pos[i]=sz;}
for(int i=sz;i>=1;i--)
{
int num=0;
for(int j=l[i];j<=n;j++)
{
++cnt[i][a[j]];
if((cnt[i][a[j]]&1)&&(cnt[i][a[j]]!=1))--num;//从2开始才计算
else if((cnt[i][a[j]]&1)==0)++num;
if(pos[j]!=pos[j+1])
f[i][pos[j]]=num;
}
}
int ans=0;
while(m--)
{
int L,R;qr(L),qr(R);L=(L+ans)%n+1,R=(R+ans)%n+1;
if(L>R)swap(L,R);int p=pos[L],q=pos[R];
if(p==q)
{
ans=0;
for(int i=L;i<=R;i++)
{
++c[a[i]];
if((c[a[i]]&1)&&(c[a[i]]!=1))--ans;
else if((c[a[i]]&1)==0)++ans;
}
for(int i=L;i<=R;i++)
if(c[a[i]])c[a[i]]=0;
}
else
{
ans=f[p+1][q-1];
for(int i=L;i<=r[p];i++)
{
++c[a[i]];
if(!v[a[i]])sta[++top]=a[i],v[a[i]]=1;
}
for(int i=l[q];i<=R;i++)
{
++c[a[i]];
if(!v[a[i]])sta[++top]=a[i],v[a[i]]=1;
}
while(top)
{
int x=sta[top--];
if((cnt[p+1][x]-cnt[q][x])!=0&&((cnt[p+1][x]-cnt[q][x])&1)&&(c[x]&1))++ans;
else if((cnt[p+1][x]-cnt[q][x])!=0&&(((cnt[p+1][x]-cnt[q][x])&1)==0)&&(c[x]&1))--ans;
else if((cnt[p+1][x]-cnt[q][x])==0&&(c[x]!=0)&&((c[x]&1))==0)++ans;
v[x]=0;c[x]=0;
}
}
qw(ans);puts("");
}
return 0;
}
最后一次更新于2019-10-14
0 条评论