做法:我们考虑前缀异或和,修改操作就变成了区间[i,n]都异或x
查询操作就变成了:区间[1,x]中有几个k
显然的分块,每个块打一个tag标记表示这个块中所有的元素都异或了tag[x]
然后处理出这个块中每种数的个数
注意查询的时候零散的块要下放标记
代码:
#include<bits/stdc++.h>
#define N 100005
#define M 334
using namespace std;
int cnt[M][N*14],sum[N],tag[M],ll[M],rr[M],a[N];
int n,Q,opt,x,y,block,num;
inline int gt(int x){return (x-1)/block+1;}
inline void pushdown(int x){
if (!tag[x]) return;
for (int i=ll[x];i<=rr[x];i++){
cnt[x][sum[i]]--;
sum[i]^=tag[x];
cnt[x][sum[i]]++;
}
tag[x]=0;
}
inline void query(int x,int y,int k){
//printf("%d %d\n",gt(x),gt(y));
int ans=0;
pushdown(gt(x));pushdown(gt(y));
if (gt(x)+1>=gt(y)){
for (int i=x;i<=y;i++) if (sum[i]==k) ans++;
}
else {
for (int i=x;i<=rr[gt(x)];i++) if (sum[i]==k) ans++;
for (int i=ll[gt(y)];i<=y;i++) if (sum[i]==k) ans++;
for (int j=gt(x)+1;j<gt(y);j++) ans+=cnt[j][k^tag[j]];
}
printf("%d\n",ans);
}
inline void change(int x,int y,int z){
int tmp=z;z=z^a[x];a[x]=tmp;
if (gt(x)+1>=gt(y)){
for (int i=x;i<=y;i++){
cnt[gt(i)][sum[i]]--;
sum[i]^=z;
cnt[gt(i)][sum[i]]++;
}
}
else {
for (int i=x;i<=rr[gt(x)];i++){
cnt[gt(i)][sum[i]]--;
sum[i]^=z;
cnt[gt(i)][sum[i]]++;
}
for (int i=ll[gt(y)];i<=y;i++){
cnt[gt(i)][sum[i]]--;
sum[i]^=z;
cnt[gt(i)][sum[i]]++;
}
for (int j=gt(x)+1;j<gt(y);j++) tag[j]^=z;
}
//for (int i=1;i<=n;i++) printf("%d %d\n",sum[i],tag[i]);
}
int main(){
scanf("%d%d",&n,&Q);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]^a[i];
block=(int)sqrt(n);num=n/block;if (n%block) num++;
for (int i=1;i<=num;i++) ll[i]=(i-1)*block+1,rr[i]=i*block;rr[num]=n;
//for (int i=1;i<=num;i++) printf("%d %d\n",ll[i],rr[i]);
for (int i=1;i<=num;i++)
for (int j=ll[i];j<=rr[i];j++) cnt[i][sum[j]]++;
while (Q--){
scanf("%d%d%d",&opt,&x,&y);
if (opt==2) query(1,x,y);
else change(x,n,y);
}
return 0;
}
- #include<bits/stdc++.h>
- #define N 100005
- #define M 334
- using namespace std;
- int cnt[M][N*14],sum[N],tag[M],ll[M],rr[M],a[N];
- int n,Q,opt,x,y,block,num;
- inline int gt(int x){return (x-1)/block+1;}
- inline void pushdown(int x){
- if (!tag[x]) return;
- for (int i=ll[x];i<=rr[x];i++){
- cnt[x][sum[i]]--;
- sum[i]^=tag[x];
- cnt[x][sum[i]]++;
- }
- tag[x]=0;
- }
- inline void query(int x,int y,int k){
- //printf("%d %d\n",gt(x),gt(y));
- int ans=0;
- pushdown(gt(x));pushdown(gt(y));
- if (gt(x)+1>=gt(y)){
- for (int i=x;i<=y;i++) if (sum[i]==k) ans++;
- }
- else {
- for (int i=x;i<=rr[gt(x)];i++) if (sum[i]==k) ans++;
- for (int i=ll[gt(y)];i<=y;i++) if (sum[i]==k) ans++;
- for (int j=gt(x)+1;j<gt(y);j++) ans+=cnt[j][k^tag[j]];
- }
- printf("%d\n",ans);
- }
- inline void change(int x,int y,int z){//[x,y]����^z
- int tmp=z;z=z^a[x];a[x]=tmp;
- if (gt(x)+1>=gt(y)){
- for (int i=x;i<=y;i++){
- cnt[gt(i)][sum[i]]--;
- sum[i]^=z;
- cnt[gt(i)][sum[i]]++;
- }
- }
- else {
- for (int i=x;i<=rr[gt(x)];i++){
- cnt[gt(i)][sum[i]]--;
- sum[i]^=z;
- cnt[gt(i)][sum[i]]++;
- }
- for (int i=ll[gt(y)];i<=y;i++){
- cnt[gt(i)][sum[i]]--;
- sum[i]^=z;
- cnt[gt(i)][sum[i]]++;
- }
- for (int j=gt(x)+1;j<gt(y);j++) tag[j]^=z;
- }
- //for (int i=1;i<=n;i++) printf("%d %d\n",sum[i],tag[i]);
- }
- int main(){
- scanf("%d%d",&n,&Q);
- for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]^a[i];
- block=(int)sqrt(n);num=n/block;if (n%block) num++;
- for (int i=1;i<=num;i++) ll[i]=(i-1)*block+1,rr[i]=i*block;rr[num]=n;
- //for (int i=1;i<=num;i++) printf("%d %d\n",ll[i],rr[i]);
- for (int i=1;i<=num;i++)
- for (int j=ll[i];j<=rr[i];j++) cnt[i][sum[j]]++;
- while (Q--){
- scanf("%d%d%d",&opt,&x,&y);
- if (opt==2) query(1,x,y);
- else change(x,n,y);
- }
- return 0;
- }