题目:Xenia and Bit Operations
传送门:http://codeforces.com/contest/339/problem/D
分析:
1)序列按,题意所给操作,从下往上,两两合并,直到只剩一个,所以这是一颗满二叉树。
2)每个节点由左右儿子更新,操作按OR和XOR交换,增加一个数组OP[]记录当前节点所需操作。
3)线段树维护修改操作,根节点的值为所求答案。
4)特殊性:只修改一个叶子节点、满二叉树。使用ZKW线段树降低代码量。
#include <bits/stdc++.h> using namespace std; const int maxN=1<<18; int T[maxN],OP[maxN]; int main(){ int n,m;scanf("%d%d",&n,&m); for(int i=0,j=1<<n;i<(1<<n);++i,++j)scanf("%d",T+j); for(int i=(1<<n)-1;i;--i){ if(OP[i])T[i]=T[i<<1]^T[(i<<1)+1];else T[i]=T[i<<1]|T[(i<<1)+1]; OP[i>>1]=!OP[i]; } for(int i=0,pi;i<m;++i){ scanf("%d",&pi);scanf("%d",T+(1<<n)+pi-1); for(int j=(1<<n)+pi-1;j>1;j>>=1) if(OP[j>>1])T[j>>1]=T[j]^T[j^1];else T[j>>1]=T[j]|T[j^1]; printf("%d\n",T[1]); } return 0; }