Codeforces Round #197 (Div. 2) D. Xenia and Bit Operations
1406 ワード
意外にも線分の木で、ここでBOBLEEにひざまずいた.
1つのRANKで深さ1を記録すると、0を取ったり、0を取ったりします.
線分ツリーの単一点更新.
1つのRANKで深さ1を記録すると、0を取ったり、0を取ったりします.
線分ツリーの単一点更新.
#include
#include
#include
#include
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 1<<19
using namespace std;
int tree[maxn<<2];
int rank[maxn<<2];
void pushup(int num)
{
if(rank[num<<1]==1)
{
rank[num]=0;
tree[num]=(tree[num<<1]|tree[num<<1|1]);
}
else {
rank[num]=1;
tree[num]=(tree[num<<1]^tree[num<<1|1]);
}
}
void build(int num,int s,int e)
{
if(s==e)
{
scanf("%d",&tree[num]);
rank[num]=1;
return;
}
int mid=(s+e)>>1;
build(lson);
build(rson);
pushup(num);
}
void update(int num,int s,int e,int pos,int val)
{
if(s==e)
{
tree[num]=val;
return;
}
int mid=(s+e)>>1;
if(pos<=mid)update(lson,pos,val);
else update(rson,pos,val);
pushup(num);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
n=(int)pow(2,(double)n);
build(1,1,n);
while(m--)
{
int pos,val;
scanf("%d%d",&pos,&val);
update(1,1,n,pos,val);
printf("%d
",tree[1]);
}
return 0;
}