gryz校赛 或和异或
问题描述
loceaner 最近在研究位运算，它研究的主要有两个：or 和 xor。 （C 语言中对于 | 和∧）
为了更好的了解这两个运算符，loceaner 找来了一个 2 ^n 长度的数组。它第一次先对所有相邻两个 数执行 or 操作，得到一个 2^n−1 长度的数组。也就是说，一开始时数组为 a[1],a[2],…,a[2 n ]，
执行完第 一次操作后，会得到 a[1] or a[2],a[3] or a[4],…,a[2 n − 1] or a[2 n ]。
第二次操作，loceaner 会将所有相邻两个数执行 xor 操作，得到一个 2 n−2 长度的数组，假如第一 次操作后的数组是 b[1],b[2],⋯,b[2 n−1 ]，那么执行完这次操作后会变成 b[1] xor b[2], b[3] xor b[4] ,⋯, b[2 n−1 − 1] xor b[2 n−1 ]。
第三次操作，loceaner 仍然将执行 or 操作，
第四次 loceaner 执行 xor 操作。如此交替进行。
最终这 2 n 个数一定会变成 1 个数。loceaner 想知道最终这个数是多少。 为了让这个游戏更好玩，loceaner 还会执行 Q 次修改操作。每次修改原先的 2 n 长度的数组中的
某一个数，对于每次修改操作，你需要输出 n 次操作后（最后一定只剩下唯一一个数）剩下的那个数 是多少。
输入
第一行两个数 n ，Q。
接下来一行 2 n 个数 a i 表示一开始的数组。
接下来 Q 行，每行两个数 x i ,y i ，表示 loceaner 这次的修改操作是将 a[x i ] 改成 y i 。
输出
Q 行，表示每次修改操作后执行 n 次操作后剩下的那个数的值。
思路
符合线段树的性质，两个合为一个，然后一直往上合，所以直接套用线段树进行解决
解法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define rson rt<<1|1
#define lson rt<<1
#define N 200010
using namespace std;
int n,m;
struct node{
int sum;
int len;
}tree[N<<2];
void push_up(int rt)
{
double x=log(tree[rt].len)/log(2);
int dep=x;
if(dep%2==1) tree[rt].sum=(tree[lson].sum|tree[rson].sum);
else tree[rt].sum=(tree[lson].sum^tree[rson].sum);
}
void build(int rt,int l,int r)
{
tree[rt].len=r-l+1;
if(l==r)
{
cin>>tree[rt].sum;
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
push_up(rt);
}
void update(int rt,int val,int l,int r,int pow)
{
if(l==r)
{
tree[rt].sum=val;
return;
}
int mid=(l+r)>>1;
if(pow<=mid) update(lson,val,l,mid,pow);
else update(rson,val,mid+1,r,pow);
push_up(rt);
}
int main()
{
cin>>n>>m;
n=(1<<n);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
update(1,y,1,n,x);//从1节点开始向下修改x号点的值为y，
cout<<tree[1].sum<<endl;
}
return 0;
}