codeforces 339 D.Xenia and Bit Operations（线段树）

    这个题目属于线段树的点更新区间查询，而且查的是整个区间，其实不用写query（）函数，只需要输出根节点保存的值就可以了。

题意：

     输入n,m表示有2^n个数和m个更新，每次更新只把p位置的值改成b，然后输出整个序列运算后的值，而这个运算就比较复杂了， 最下面一层两个数字之间或运算得到原来数目一半的数字，然后两个之间异或运算，得到一半，再或再异或………………，一直到得到一个数字，这个数字就是要求的结果。

思路：

     如果只是一种运算，这就是简单的线段树点更新，区间查询。而现在，我们要确定什么时候用or 什么时候用xor， 想想看，最下面一层是用or， 总共有n层，因为or和xor是交替进行的，我们就可以用n确定每层的运算，然后在建树和更新的时候分情况讨论。

代码如下：

#include <stdio.h>
#include <string.h>
const int maxn = (1<<17) + 5;

struct node
{
    int l, r;
    int x;
}tree[maxn<<2];
int arr[maxn];

void build(int l, int r, int o, int d)
{
    tree[o].l = l;
    tree[o].r = r;
    if (l == r)
    {
        tree[o].x = arr[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, o<<1, -d);
    build(mid+1, r, o<<1|1, -d);
    if (d == 1)
        tree[o].x = tree[o<<1].x^tree[o<<1|1].x;
    else
        tree[o].x = tree[o<<1].x|tree[o<<1|1].x;
 }

 int query(int l, int r, int o)
 {
     if (tree[o].l == l && tree[o].r == r)
        return tree[o].x;
     int mid = (tree[o].l + tree[o].r) >> 1;
     if (r <= mid)
        return query(l, r, o<<1);
     else if (l > mid)
        return query(l, r, o<<1|1);
     else
        return query(l, mid, o<<1)^query(mid+1, r, o<<1|1);
 }

 void update(int x, int v, int o, int d)
 {
     if (tree[o].l == tree[o].r && tree[o].l == x)
     {
        tree[o].x = v;
        return;
     }
     int mid = (tree[o].l + tree[o].r) >> 1;
     if (x <= mid)
        update(x, v, o<<1, -d);
     else
        update(x, v, o<<1|1, -d);
     if (d == 1)
        tree[o].x = tree[o<<1].x^tree[o<<1|1].x;
     else
        tree[o].x = tree[o<<1].x|tree[o<<1|1].x;
 }

 int main()
 {
     int n, m;
     int p, b, d;
     while (scanf("%d %d", &n, &m) != EOF)
     {
         int num = 1<<n;
         for (int i = 1; i <= num; i++)
            scanf("%d", &arr[i]);
         if (n&1)
            d = -1;
         else
            d = 1;
         build(1, num, 1, d);
         while (m--)
         {
             scanf("%d %d", &p, &b);
             update(p, b, 1, d);
             printf("%d\n", query(1, num, 1));
         }
     }
     return 0;
 }

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/10380575