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

题目链接

题意:给出n和m,初始给出1<<n个数,先相邻的两个数进行或操作(a[1]^a[2],a[3]^a[4]…),得到的新数列再相邻的两个数进行异或操作

最后得到一个数,即为答案。现在给出m个操作,每个操作两个数p,b,表示令a[p]=b,每次变化后输出最终的结果。

思路:线段树。这道题让我学到了,线段树的数组tree[i]存储的信息可能不唯一,可以不同层存储的是不同的信息。

比如这道题中,距离叶子节点距离为奇数的点存储的是或操作的结果,距离叶子节点距离为偶数的点存储的是异或操作的结果。

还需要注意的是,build和update操作都是从顶向下,最后一个操作是异或还是或取决于n的奇偶性,记得判断。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz