codeforces 339 D.Xenia and Bit Operations(线段树)

举报
xindoo 发表于 2022/04/16 00:09:03 2022/04/16
【摘要】     这个题目属于线段树的点更新区间查询,而且查的是整个区间,其实不用写query()函数,只需要输出根节点保存的值就可以了。 题意:      输入n,m表示有2^n个数和m个更新,每次更新只把p位置的值改成b,然后输出整个序列运算后的值,而这个运算就比较复杂了, 最下面一层两个...

    这个题目属于线段树的点更新区间查询,而且查的是整个区间,其实不用写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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。