[codeforces 339D]Xenia and Bit Operations

题目:Xenia and Bit Operations

传送门:http://codeforces.com/contest/339/problem/D

分析:

1)序列按,题意所给操作,从下往上,两两合并,直到只剩一个,所以这是一颗满二叉树。

2)每个节点由左右儿子更新,操作按OR和XOR交换,增加一个数组OP[]记录当前节点所需操作。

3)线段树维护修改操作,根节点的值为所求答案。

4)特殊性:只修改一个叶子节点、满二叉树。使用ZKW线段树降低代码量。

#include <bits/stdc++.h>
using namespace std;
const int maxN=1<<18;
int T[maxN],OP[maxN];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=0,j=1<<n;i<(1<<n);++i,++j)scanf("%d",T+j);
    for(int i=(1<<n)-1;i;--i){
        if(OP[i])T[i]=T[i<<1]^T[(i<<1)+1];else T[i]=T[i<<1]|T[(i<<1)+1];
        OP[i>>1]=!OP[i];
    }
    for(int i=0,pi;i<m;++i){
        scanf("%d",&pi);scanf("%d",T+(1<<n)+pi-1);
        for(int j=(1<<n)+pi-1;j>1;j>>=1)
            if(OP[j>>1])T[j>>1]=T[j]^T[j^1];else T[j>>1]=T[j]|T[j^1];
        printf("%d\n",T[1]);
    }
    return 0;
} 

 

上一篇:Linux文件系统剖析


下一篇:黑猫带你学eMMC协议第20篇:eMMC的后台操作(Background Operations)