CodeForces 339D Xenia and Bit Operations (线段树)

题意：给定 2的 n 次方个数，对这些数两个两个的进行或运算，然后会减少一半的数，然后再进行异或运算，又少了一半，然后再进行或运算，再进行异或，不断重复，到最后只剩下一个数，要输出这个数，然后有 m 个询问，

每个询问有 p 和 b，要求把第 p 个数改成 b，再这样运算，输出结果。

析：这个题是不是很像线段树，不过这个题不是随机询问哪个区间，区间是固定的，这样也就简单了很多，就省下了一个query函数，再就是线段树是从上到下的，所以我们要分好到底是异或还是或，然后就很简单了，

其实这个题也可以这样想，也是先构造一棵树，然后再考虑从下到上进行变，因为要改变值，所以先把最下面的改掉，然后再更新上去，这样次数比线段树少，比它更快一点，其实原理也是一样的。

代码如下：

线段树：

#include <bits/stdc++.h>

#define lson l,m,rt<<1,!ok

#define rson m+1,r,rt<<1|1,!ok

using namespace std;

const int maxn = (1 << 17) + 5;

int sum[maxn<<2];

void pushup(int rt, bool ok){

    if(ok)  sum[rt] = sum[rt<<1] | sum[rt<<1|1];

    else  sum[rt] = sum[rt<<1] ^ sum[rt<<1|1];

}

void build(int l, int r, int rt, bool ok){

    if(l == r){

        scanf("%d", &sum[rt]);

        return ;

    }

    int m = (l+r) >> 1;

    build(lson);

    build(rson);

    pushup(rt, ok);

}

void update(int p, int b, int l, int r, int rt, bool ok){

    if(l == r){

        sum[rt] = b;

        return ;

    }

    int m = (l+r) >> 1;

    if(p <= m)  update(p, b, lson);

    else  update(p, b, rson);

    pushup(rt, ok);

}

int main(){

    int num, mm;

    cin >> num >> mm;

    int n = (1 << num);

    bool ok = (num & 1);

    build(1, n, 1, ok);

    while(mm--){

        int p, b;

        scanf("%d %d", &p, &b);

        update(p, b, 1, n, 1, ok);

        printf("%d\n", sum[1]);

    }

    return 0;

}

另一种：

#include <bits/stdc++.h>

using namespace std;

const int maxn = (1 << 18) + 5;

int a[maxn];

int num;

int main(){

    int n, m;

    cin >> n >> m;

    num = 1 << n;

    for(int i = 0; i < num; ++i)  scanf("%d", &a[i+num]);//构造一棵树

    int cnt = 0;

    int t = num;

    while(t){//把所有的值算一下

        t >>= 1;

        for(int i = 0; i < t; ++i)

            if(cnt & 1)   a[t+i] = a[(t+i)<<1] ^ a[(t+i)<<1|1];

            else  a[t+i] = a[(t+i)<<1] | a[(t+i)<<1|1];

        ++cnt;//控制是或还是异或

    }

    while(m--){

        int p, b;

        scanf("%d %d", &p, &b);

        cnt = 0;  p += num-1;

        a[p] = b;

        while(p){//从下到上更新

           p >>= 1;

           if(cnt & 1)  a[p] = a[p<<1] ^ a[p<<1|1];

           else  a[p] = a[p<<1] | a[p<<1|1];

           ++cnt;

        }

        printf("%d\n", a[1]);

    }

    return 0;

}

巴特西

CodeForces 339D Xenia and Bit Operations (线段树)

最新文章

热门文章