题目描述
LYK最近在研究位运算，它研究的主要有两个：or和xor。（C语言中对于|和^）
为了更好的了解这两个运算符，LYK找来了一个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]。
第二次操作，LYK会将所有相邻两个数执行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)]。
第三次操作，LYK仍然将执行or操作，第四次LYK执行xor操作。如此交替进行。
最终这2^n个数一定会变成1个数。LYK想知道最终这个数是多少。
为了让这个游戏更好玩，LYK还会执行Q次修改操作。每次修改原先的2^n长度的数组中的某一个数，对于每次修改操作，你需要输出n次操作后（最后一定只剩下唯一一个数）剩下的那个数是多少。
输入格式(xor.in)
第一行两个数n，Q。
接下来一行2^n个数ai表示一开始的数组。
接下来Q行，每行两个数xi,yi，表示LYK这次的修改操作是将a{xi}改成yi。
输出格式(xor.out)
Q行，表示每次修改操作后执行n次操作后剩下的那个数的值。
输入样例
2 4
1 6 3 5
1 4
3 4
1 2
1 2
输出样例
1
3
3
3
样例解释
第一次修改，{4,6,3,5}->{6,7}->{1}
第二次修改，{4,6,4,5}->{6,5}->{3}
第三次修改，{2,6,4,5}->{6,5}->{3}
第四次修改，{2,6,4,5}->{6,5}->{3}
对于30%的数据n<=17，Q=1。
对于另外20%的数据n<=10，Q<=1000。
对于再另外30%的数据n<=12，Q<=100000。
对于100%的数据1<=n<=17，1<=Q<=10^5，1<=xi<=2^n，0<=yi<2^30，0<=ai<2^30。
分析：考试的时候这道题是T3,题面又很长，就没信心做下去直接打了个暴力，竟然还有50分，现在看，竟然就是一道裸的线段树的题......
它的每一次操作都对应线段树的合并操作，我们只需要记录一下深度，看看进行哪一次操作就可以了.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n, q,maxn,c[]; void build(int o, int l, int r, int dep)
{
if (l == r)
{
scanf("%d", &c[o]);
return;
}
int mid = (l + r) >> ;
build(o * , l, mid, dep + );
build(o * + , mid + , r, dep + );
if ((n - dep + ) % == )
c[o] = c[o * ] | c[o * + ];
else
c[o] = c[o * ] ^ c[o * + ];
} void update(int o, int l, int r, int x, int v, int dep)
{
if (l == r)
{
c[o] = v;
return;
}
int mid = (l + r) >> ;
if (x <= mid)
update(o * , l, mid, x, v, dep + );
if (x > mid)
update(o * + , mid + , r, x, v, dep + );
if ((n - dep + ) % == )
c[o] = c[o * ] | c[o * + ];
else
c[o] = c[o * ] ^ c[o * + ];
} int main()
{
scanf("%d%d", &n, &q);
maxn = ( << n);
build(, , maxn,);
for (int i = ; i <= q; i++)
{
int x, y;
scanf("%d%d", &x, &y);
update(, , maxn, x, y, );
printf("%d\n", c[]);
} return ;
}