link
题意:
给定一个序列,两种操作,一种区间异或上一个常量x,第二种是区间异或上常量x+一个从0开始的等差数列。
思路:
第一种操作很好维护,通过差分数组来维护,就类似于加法的差分数组,第二种呢,严格意义上来说就是对于一个数y ^ (x+i),貌似不是很好维护,那么我们考虑异或的性质,如果i当前小于x的lowbit,那么加号和异或是等价的,可以直接变成y ^ x ^ i ,如果这样的话那么就好操作了,我们考虑一段一段的区间,把当前的l,r分为不超过log的区间,每一段区间都是x的lowbit,那么就和第一种操作是等价的了,那么对于一个等差数列怎么维护呢?我们可以通过类似于线段树懒标记的手法打tag,pushdown也是很好的,b[i][j]代表从[i,i+(1<<j))之间是否异或上了从0开始的等差数列,那么pushdown也很好操作。
// Problem: Kuriyama Mirai and Exclusive Or
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11254/I
// Memory Limit: 131072 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//#pragma GCC target("avx")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
// created by myq
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef pair<int,int> pii;
const int N = 600010;
const int mod=998244353;
inline int read()
{
int res=0;
int f=1;
char c=getchar();
while(c>'9' ||c<'0')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
res=(res<<3)+(res<<1)+c-'0';
c=getchar();
}
return res;
}
int b[N][20];
int tag[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,q;
cin>>n>>q;
for(int i=1,x;i<=n;i++)
{
cin>>x;
tag[i]^=x;
tag[i+1]^=x;
}
while(q--)
{
int op,l,r,x;
cin>>op>>l>>r>>x;
if(op==0){
tag[l]^=x;
tag[r+1]^=x;
continue;
}
else
{
for(int i=0;i<=19;i++){
if((x>>i&1)&&l+(1<<i)-1<=r)
{
b[l][i]^=1;
tag[l]^=x;
tag[l+(1<<i)]^=x;
x+=(1<<i);
l+=(1<<i);
}
}
for(int i=19;i>=0;i--)
{
if(l+(1<<i)-1<=r)
{
b[l][i]^=1;
tag[l]^=((x>>i)<<i);
tag[l+(1<<i)]^=((x>>i)<<i);
l+=(1<<i);
x+=(1<<i);
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=19;j>=1;j--){
if(!b[i][j]) continue;
b[i][j-1]^=1;
if(i+(1<<j-1)<=n)
{
tag[i+(1<<j-1)]^=(1<<j-1);
b[i+(1<<j-1)][j-1]^=1;
if(i+(1<<j)<=n)
{
tag[i+(1<<j)]^=(1<<j-1);
}
}
}
}
for(int i=1;i<=n;i++)
cout<<(tag[i]^=tag[i-1])<<" ";
return 0;
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/