2906: 颜色

Time Limit: 30 Sec  Memory Limit: 512 MB

Submit: 141  Solved: 51

[][][]

Description

给定一个长度为N的颜色序列C，对于该序列中的任意一个元素Ci，都有1<=Ci<=M。对于一种颜色ColorK来说，区间[L,R]内的权值定义为这种颜色在该区间中出现的次数的平方，即区间[L,R]内中满足Ci=ColorK的元素个数的平方。接下来给出Q个询问，询问区间[L,R]内颜色[a,b]的权值总和。

 

 

Input

第1行三个整数N,M,Q。分别代表序列长度，颜色总数和询问总数。

第2行N个整数，代表序列Ci。

第3行到第Q+2行，每行4个整数l,r,a,b。记上一次计算出的答案为Lans。那么实际的l,r,a,b为给出的l,r,a,b xor上Lans。第一个询问的时候Lans=0。

 

 

Output

总共Q行，对于每一个询问，输出权值总和

Sample Input

4 2 3

1 1 2 2

1 4 1 2

10 11 9 10

3 0 0 0

Sample Output

8

2

0

HINT

 

1<=N,Q<=50000,M<=20000

//对序列分块  预处理出l-r块k出现的次数 方便暴力边角//sum记录k权值的前缀和 方便o(1)查询权值在a-b的权值和 然后普通分块即可 #include 
      
       #define N 50005#define M 20005#define ll long longusing namespace std;ll readll(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int readint(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return f*x;}int p[N],size,n,m,q,a[N];ll sum[40][40][M];int  ans[40][40][M];ll num[M];void advance(){	for(int i=1;i<=p[n];i++){		for(int j=(i-1)*size+1;j<=min(n,i*size);j++) ans[i][i][a[j]]++;		for(int j=1;j<=m;j++) sum[i][i][j]+=ans[i][i][j]*ans[i][i][j];		for(int j=1;j<=m;j++) sum[i][i][j]+=sum[i][i][j-1];		for(int j=i+1;j<=p[n];j++){			for(int k=1;k<=m;k++) ans[i][j][k]=ans[i][j-1][k],sum[i][j][k]=sum[i][j-1][k];			for(int k=(j-1)*size+1;k<=min(n,j*size);k++) num[a[k]]+=(2*ans[i][j][a[k]]+1),ans[i][j][a[k]]++;			//for(int k=(j-1)*size+1;k<=min(n,size*j);k++) ans[i][j][a[k]]++;			for(int k=1;k<=m;k++) num[k]+=num[k-1],sum[i][j][k]+=num[k];			for(int k=1;k<=m;k++) num[k]=0;		} 	}}ll slove(int l,int r,int t,int b){	ll ans1=0;	if(p[r]==p[l]){		for(int i=l;i<=min(r,p[l]*size);i++){			if(a[i]>=t&&a[i]<=b){			ans1+=(2*num[a[i]]+1);num[a[i]]++;}		}		for(int i=l;i<=min(r,p[l]*size);i++) num[a[i]]=0;		return ans1;	}	else if(p[r]-p[l]==1){		for(int i=l;i<=min(r,p[l]*size);i++){			if(a[i]>=t&&a[i]<=b){			ans1+=(2*num[a[i]]+1);num[a[i]]++;}		}		for(int i=(p[r]-1)*size+1;i<=r;i++){			if(a[i]>=t&&a[i]<=b) {			ans1+=(2*num[a[i]]+1);num[a[i]]++;}		}		for(int i=l;i<=min(r,p[l]*size);i++) num[a[i]]=0;		for(int i=(p[r]-1)*size+1;i<=r;i++) num[a[i]]=0;		return ans1;	}	ans1=sum[p[l]+1][p[r]-1][b]-sum[p[l]+1][p[r]-1][t-1];	for(int i=l;i<=min(r,p[l]*size);i++) num[a[i]]=ans[p[l]+1][p[r]-1][a[i]];	for(int i=(p[r]-1)*size+1;i<=r;i++) num[a[i]]=ans[p[l]+1][p[r]-1][a[i]];	for(int i=l;i<=min(r,p[l]*size);i++) {	if(a[i]>=t&&a[i]<=b) ans1+=(2*num[a[i]]+1),num[a[i]]++;}	for(int i=(p[r]-1)*size+1;i<=r;i++) {	if(a[i]>=t&&a[i]<=b) ans1+=(2*num[a[i]]+1),num[a[i]]++;}	for(int i=l;i<=min(r,p[l]*size);i++) num[a[i]]=0;	for(int i=(p[r]-1)*size+1;i<=r;i++) num[a[i]]=0;	return ans1;}int main(){	ios::sync_with_stdio(false);	n=readint();m=readint();q=readint();	size=(int)(ceil(pow(n,2.0/3)));	for(int i=1;i<=n;i++){		a[i]=readint();p[i]=(i-1)/size+1;	}	advance();ll Lans=0;	int l,r,t,b;//	cout<
       
        <<" "<
        
         <