Lvat_s Blog

第一次写分块，挑了这题写……

然后调了一个晚上。

各种猎奇的错误都被我犯了……

人傻就是要多做题。

分块+二分

参考hzwer的

弱智错误记录:

1.数组要注意清空:这个在WC2016上已经让我的T1 60->0了……以后要认真吸取教训

2.不要乱开局部数组:这样会显著增大常数

3.要知道自己二分的是什么，不要搞着搞着就搞乱了

以上

Claris也在坚持刷题……太可怕了，本身实力超强还在刷……orzzzz

#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

int n,c,m,a[100005],f[1505][1505],fir[100005],las[100005],block,ans=0,L[1505],R[1505],belong[100005],tmp[100005],cnt;

struct Data{
int a,b;
friend bool operator<(Data a,Data b){
return (a.a<b.a)||(a.a==b.a && a.b<b.b);
}
}data[100005];

pair<int,int> GetLR(int L,int R){
L=(L+ans)%n+1;
R=(R+ans)%n+1;
if(L>R)swap(L,R);
return make_pair(L,R);
}

void Pre(){
for(int i=1;i<=cnt;i++){
	for(int j=L[i];j<=n;j++)tmp[a[j]]=0;
	int tot=0;
	for(int j=L[i];j<=n;j++){
		if(tmp[a[j]]%2==0 && tmp[a[j]])tot--;
		tmp[a[j]]++;
		if(tmp[a[j]]%2==0)tot++;
		f[i][belong[j]]=tot;
	}
}
//for(int i=belong[1];i<=belong[n];i++){for(int j=i;j<=belong[n];j++){printf("%d ",f[i][j]);}putchar('\n');}
for(int i=1;i<=n;i++)data[i].a=a[i],data[i].b=i;
sort(data+1,data+n+1);
for(int i=1;i<=n;i++){
	if(fir[data[i].a]==0)fir[data[i].a]=i;
	las[data[i].a]=i ;
}
}

int Ef_Fir(int x,int v){
int tp=214748364,l=fir[v],r=las[v];
while(l<=r){
	int mid=l+r>>1;
	if(x>data[mid].b)l=mid+1;
	else {r=mid-1;tp=mid;}
}
return tp;
}

int Ef_Las(int x,int v){
int tp=0,l=fir[v],r=las[v];
while(l<=r){
	int mid=l+r>>1;
	if(x<data[mid].b)r=mid-1;
	else {l=mid+1;tp=mid;}
}
return tp;
}

int Ef(int x,int y,int v){
//printf("%d %d %d | EF:%d %d\n",x,y,v,Ef_Las(y,v),Ef_Fir(x,v));
return max(Ef_Las(y,v)-Ef_Fir(x,v)+1,0);
}

int solve(int l,int r){
//printf("LR:%d %d\n",l,r);
int nwans=0,kl=belong[l],kr=belong[r];
if(kl+1==kr || kl==kr){
	for(int i=l;i<=r;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]);
		if(sp%2==0){nwans++;}
		//printf("%d %d %d\n",l,r,a[i]);
		tmp[a[i]]=1;
	}
	for(int i=l;i<=r;i++)tmp[a[i]]=0;
	return nwans;
}
else {
    int fs=L[kl+1],la=R[kr-1];
    nwans=f[kl+1][kr-1];
    //printf("%d %d | NW_ANS1:%d\n",kl,kr,nwans);
    for(int i=l;i<fs;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]),sp2=Ef(fs,la,a[i]);
		if(sp2%2==0 && sp%2 && sp2!=0){nwans--;}
		if((sp2%2 || sp2==0) && sp%2==0){nwans++;}
		//printf("SP:%d SP2:%d_%d_",sp,sp2,nwans);
		tmp[a[i]]=1;
    }
    //printf("NW_ANS2:%d\n",nwans);
    for(int i=la+1;i<=r;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]),sp2=Ef(fs,la,a[i]);
		if(sp2%2==0 && sp%2 && sp2!=0){nwans--;}
		if((sp2%2 || sp2==0) && sp%2==0){nwans++;}
		//printf("SP:%d SP2:%d_%d_",sp,sp2,nwans);
		tmp[a[i]]=1;
    }
    for(int i=l;i<fs;i++)tmp[a[i]]=0;
    for(int i=la+1;i<=r;i++)tmp[a[i]]=0;
    return nwans;
}
}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("2821.in","r",stdin);
freopen("2821.out","w",stdout);
Read(n);Read(c);Read(m);
for(int i=1;i<=n;i++){
	Read(a[i]);
}
block=(int)sqrt((double)n/log(n)*log(2));
cnt=n/block+(n%block!=0);
for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;
for(int i=1;i<=cnt;i++)L[i]=R[i-1]+1,R[i]=i*block;
R[cnt]=n;
Pre();
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=m;i++){
	int tl,tr;
	Read(tl);Read(tr);
    pair<int,int> Ask=GetLR(tl,tr);
    //pair<int,int> Ask=make_pair(tl,tr);
    ans=solve(Ask.first,Ask.second);
    printf("%d\n",ans);
}
return 0;
}