Codeforces Round #197 (Div. 2) D. Xenia and Bit Operations


意外にも線分の木で、ここでBOBLEEにひざまずいた.
1つのRANKで深さ1を記録すると、0を取ったり、0を取ったりします.
線分ツリーの単一点更新.
#include 
#include 
#include 
#include 
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 1<<19
using namespace std;

int tree[maxn<<2];
int rank[maxn<<2];

void pushup(int num)
{
    if(rank[num<<1]==1)
    {
        rank[num]=0;
        tree[num]=(tree[num<<1]|tree[num<<1|1]);
    }
    else {
        rank[num]=1;
        tree[num]=(tree[num<<1]^tree[num<<1|1]);
    }

}

void build(int num,int s,int e)
{
    if(s==e)
    {
        scanf("%d",&tree[num]);
        rank[num]=1;
        return;
    }
    int mid=(s+e)>>1;

    build(lson);
    build(rson);

    pushup(num);
}

void update(int num,int s,int e,int pos,int val)
{
    if(s==e)
    {
        tree[num]=val;
        return;
    }
    int mid=(s+e)>>1;

    if(pos<=mid)update(lson,pos,val);
    else update(rson,pos,val);

    pushup(num);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    n=(int)pow(2,(double)n);

    build(1,1,n);

    while(m--)
    {
        int pos,val;

        scanf("%d%d",&pos,&val);
        update(1,1,n,pos,val);
        printf("%d
",tree[1]); } return 0; }