CF 197 DIV2 Xenia and Bit Operations 线段树

时间:2024-07-02 17:07:08

线段树!!1A

代码如下:

 #include<iostream>
#include<cstdio>
#define lson i<<1
#define rson i<<1|1
#define MAX 140000
#define ll __int64
using namespace std;
ll a[MAX],s;
struct tree
{
int l,r;
ll res;
bool flag;
}T[*MAX];
//奇数OR,偶数XOR
void built(int i,int l,int r,bool f)
{
T[i].l=l;
T[i].r=r;
T[i].flag=f;
if(l==r){
T[i].res=a[l];
return ;
}
int m=(l+r)>>;
built(lson,l,m,!f);
built(rson,m+,r,!f);
if(T[i].flag) T[i].res=T[lson].res|T[rson].res;
else T[i].res=T[lson].res^T[rson].res;
}
void update(int i,int d,ll p)
{
if(T[i].l==d&&T[i].r==d){
T[i].res=p;
return ;
}
int m=(T[i].l+T[i].r)>>;
if(d<=m) update(lson,d,p);
else if(d>m) update(rson,d,p);
if(T[i].flag) T[i].res=T[lson].res|T[rson].res;
else T[i].res=T[lson].res^T[rson].res;
}
int main()
{
int n,m,i,k;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=;i<=(<<n);i++) scanf("%I64d",&a[i]);
built(,,(<<n),n&);
for(i=;i<m;i++){
scanf("%d %I64d",&k,&s);
update(,k,s);
printf("%I64d\n",T[].res);
}
}
return ;
}