https://www.codechef.com/DEC17/problems/CHEFEXQ
题意：
位置i的数改为k
询问区间[1,i]内有多少个前缀的异或和为k
分块
sum[i][j] 表示第i块内，有多少个前缀，他们的异或和为j
a[i] 表示 位置i的数
位置i改为k：
若 g=x1^x2^x3……
把 x1 改为 k 后，那新的g=x1^x1^k^x2^x3……
所以修改可以看做整体异或 修改后的值^原来的值
即
区间[i，n] 异或上a[i]^k
i所在块单个改，后面的块整体打标记
查询：
i所在块单个查
前面的块 累加sum[][k^标记]
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001
#define S 318
const int K=<<; int sum[S][K+]; int tag[S]; int a[N],prexo[N]; int bl[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
int n,q;
read(n); read(q);
for(int i=;i<=n;++i)
{
read(a[i]);
prexo[i]=prexo[i-]^a[i];
}
int siz=sqrt(n);
for(int i=;i<=n;++i)
{
bl[i]=(i-)/siz+;
sum[bl[i]][prexo[i]]++;
}
int tot=bl[n];
int ty,x,k;
int m,res,pos;
int ans;
while(q--)
{
read(ty); read(x); read(k);
pos=bl[x];
if(ty==)
{
res=a[x]^k;
a[x]=k;
m=min(pos*siz,n);
if(tag[pos])
{
for(int i=(pos-)*siz+;i<=m;++i)
{
sum[pos][prexo[i]]--;
prexo[i]^=tag[pos];
sum[pos][prexo[i]]++;
}
tag[pos]=;
}
for(int i=x;i<=m;++i)
{
sum[pos][prexo[i]]--;
prexo[i]^=res;
sum[pos][prexo[i]]++;
}
for(int i=pos+;i<=tot;++i) tag[i]^=res;
}
else
{
ans=;
for(int i=(pos-)*siz+;i<=x;++i)
{
if((prexo[i]^tag[pos])==k) ans++;
}
for(int i=;i<pos;++i) ans+=sum[i][k^tag[i]];
cout<<ans<<'\n';
}
}
}
Read problems statements in Mandarin chinese, Russian andVietnamese as well.
Chef always likes to play with arrays. He came up with a new term "magical subarray". A subarray is called magical if its starting index is 1 (1-based indexing). Now, Chef has an array of N elements and 2 types of queries:
- type 1: Given two numbers i and x, the value at index i should be updated to x.
- type 2: Given two numbers i and k, your program should output the total number ofmagical subarrays with the last index ≤ i in which the xor of all elements is equal tok.
Input
- The first line of the input contains two integers N and Q denoting the number of elements in the array and the number of queries respectively.
- The second line contains N space-separated integers A1, A2 ... AN denoting the initial values of the array.
- Each of the following Q lines describes an operation. If the first integer is 1, it means that the operation is of type 1 and it will be followed by two integers i and x. If the first integer is 2, it means that the operations is of type 2 and it will be followed by two integers i and k.
Output
For each operation of type 2, print the number of magical subarrays on a separate line.
Constraints
- 1 ≤ N, Q ≤ 100,000
- 1 ≤ A[i] ≤ 1,000,000
- 1 ≤ i ≤ N
- 1 ≤ x, k ≤ 1,000,000
Subtasks
Subtask #1 (20 points): 1 ≤ N, Q ≤ 1,000
Subtask #2 (30 points): 1 ≤ N, Q ≤ 10,000
Subtask #3 (50 points): original constraints
Example
Input: 5 3
1 1 1 1 1
2 5 1
1 3 2
2 5 1 Output: 3
1