CF339D Xenia and Bit Operations

题意：

有$2^n$个数，有$m$个操作，每次修改一个数，然后你要输出$((a1|a2)xor(a3|a4))|((a5|a6)xor(a7|a8))....$

即$or$ $xor$ 交替计算。

第一行两个数字$n,m$。

第二行$2^n$ 个数字。

下面$m$行，每行两个数字$x,y$，将第$x$个数字改为$y$。

保证$1\le n\le 17,1\le m\le 10^5$ ，数字任意时刻满足$0\le x\le 2^{30}$

共$m$行，输出每次改完数字后上述表达式的值。

思路：

考虑线段树解决，单点修改十分容易。 重点在于如何在$pushup$中维护答案。 通过观察可以发现，$pushup$中

左右区间合并时，长度为$2$的奇数次幂的区间合并$pushup$需要$|$操作。左右区间合并时，长度为$2$的偶数次幂的区间合并$pushup$需要$xor$操作。

因此，$pushup$中分类讨论即可解决问题。

Code:

#include<stdio.h> #include<iostream> #include<string.h> #include<cstring> #include<string> #include<math.h> #include<algorithm> #include<bits/stdc++.h> #include<map> #include<vector> #include<cmath> #include<queue> #include<set> #define cuttime ios::sync_with_stdio(false) #define swap(x, y) x ^= y, y ^= x, x^= y #define INF 0x3f3f3f3f #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define dep(i,a,b) for(int i=(a);i>=(b);--i) #define scan1(x) scanf("%d",&x) #define scan2(x,y) scanf("%d%d",&x,&y) #define scan3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define scanll1(x) scanf("%lld",&x) #define scanll2(x,y) scanf("%lld%lld",&x,&y) #define scanll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z) #define lowbit(x) (x&(-x)) #define mid ((l+r)>>1) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define debug(x) cout <<#x<<": "<<x<<endl using namespace std; typedef unsigned long long ull; typedef long long ll; const int N=5e5+20; const int MAX=10000007; inline ll read() { char c=getchar();ll x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();} return x*f; } inline void out(ll x) { if(x>9) out(x/10); putchar(x%10+'0'); } ll a[N]; ll sum[N]; ll tree[N]; /** * 线段树 * @param a [description] * @param b [description] * @return [description] */ ll qsm(ll a,ll b){ ll ans=1; while(b){ if(b&1){ ans=ans*a; } a=a*a; b>>=1; } return ans; } void pushup(int l,int r,int rt){ int mi; rep(i,1,32){ if(qsm(2,i)==(r-l+1)){ mi=i; break; } } if(mi%2){ tree[rt]=(tree[rt<<1]|tree[rt<<1|1]); } else{ tree[rt]=(tree[rt<<1]^tree[rt<<1|1]); } } void build(int l,int r,int rt){ if(l==r){ tree[rt]=a[l]; return ; } build(lson); build(rson); pushup(l,r,rt); } void update(int L,int R,int l,int r,int rt,int val){ if(L<=l&&r<=R){ a[l]=val; tree[rt]=val; return ; } if(L<=mid)update(L,R,lson,val); if(R>mid)update(L,R,rson,val); pushup(l,r,rt); } map<ll,ll>mp; int n,m; int main(){ int n,m; scan2(n,m); rep(i,1,qsm(2,n)){ a[i]=read(); } build(1,qsm(2,n),1); rep(i,1,m){ int x,y; scan2(x,y); update(x,x,1,qsm(2,n),1,y); out(tree[1]); puts(""); } return 0; }