Codeforces 339D Xenia and Bit Operations

题目链接:http://codeforces.com/contest/339/problem/D

题意:给你一个2^n长度的序列,每次序列重复进行如下两个操作:1.将相邻两项或起来得到一个新数字扔进新的序列里,2.将相邻两项异或起来得到一个新数字扔进新的序列里,两个操作交替进行,那么一次操作后,序列长度缩减为原来的一半,如此迭代下去直到只剩一个数,这个数就是该序列的价值,现在还要求你支持单点修改然后输出序列的价值。

思路:仔细思考一下发现这就是一个模拟线段树pushup的过程,相当于该线段树有2^n个叶子节点,然后每次交替pushup上去直到根节点,同时也支持单点更新,然后就做完了。

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=(1<<17)+10;
int n,m,i,s,p,b,val[N<<2];
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
void pushup(int root,int op){
    if (op==0) val[root]=val[root<<1]|val[root<<1|1];
    else val[root]=val[root<<1]^val[root<<1|1];
}
void build(int root,int l,int r,int op){
    if (l==r){
        read(val[root]);
        return;
    }
    int mid=l+((r-l)>>1);
    build(lson,op^1);
    build(rson,op^1);
    pushup(root,op);
}
void update(int root,int l,int r,int pos,int v,int op){
    if (l==r){
        val[root]=v;
        return;
    }
    int mid=l+((r-l)>>1);
    if (pos<=mid) update(lson,pos,v,op^1);
    else update(rson,pos,v,op^1);
    pushup(root,op);
}
int main(){
    read(n),read(m);
    if (n&1) s=0;
    else s=1;
    n=1<<n;
    build(1,1,n,s);
    for (i=1;i<=m;i++){
        read(p),read(b);
        update(1,1,n,p,b,s);
        printf("%d\n",val[1]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注