xindoo is
always here

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 » codeforces 339 D.Xenia and Bit Operations(线段树)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏