[BZOJ4811]由乃的OJ

题目大意

给你一个有n个点的树,每个点的包括一个位运算opt和一个权值x,位运算有&,l,^三种,分别用1,2,3表示。
有修改和询问两种共m次操作。
每次询问包含三个数x,y,z,初始选定一个数v。然后v依次经过从x到y的所有节点,每经过一个点i,v就变成v opti xi,所以他想问你,最后到y时,希望得到的值尽可能大,求最大值?给定的初始值v必须是在[0,z]之间。
每次修改包含三个数x,y,z,意思是把x点的操作修改为y,数值改为z。
$k<=64$ $x,y,z<2^k$

Solution

其实就是在树上的带修的多次询问的起床困难综合症
那道题的方法就是对每一位看一下初值每一位填0和填1哪个更优。多次询问拿到树上就是树链剖分,对每一段连续的区间用线段树维护出初值每一位取0,取1后这一段区间这一位的值。这样的空间复杂度是$O(64n)$,时间复杂度是$O(nk{log_n}^2)$,光荣地TLE(MLE也有可能)。

考虑怎么把每一位的信息合并。其实只要初值是0和(2^k-1)后计算出来的答案是有用的。两种答案分别记为a0,a1。那么初值第i位取0的话,最后这一位就会得到a0的第i位;取1的话,最后得到a1的第i位。
这样我们只要计算a0和a1两个值,时间复杂度变为了$O(n{log_n}^2)$。现在只需思考怎样在线段树上维护这个值。叶子节点的信息非常显然。合并两个节点时,左右节点信息分别记为al0,al1,ar0,ar1。那么a0在左边变为1的位到右边会变为ar1,答案为$al0\And ar1$;a0在左边变为0的位到右边会变为ar0,答案为$(!al0)\And ar0$。所以$a0=(al0\And ar1)|((!al0)\And ar0)$。同理,$a1=(vx.a1\And vy.a1)|((!vx.a1)\And vy.a0)$。
剩下只剩下一些小小的细节了。比如u->v的链和v->u的链是不一样的。树剖要把两条链分开写,线段树也要维护一段区间的从左到右的值和从右到做的值。等等。

Code

2 条评论
  1. 黄队长太强了

  2. My husband and i ended up being excited Michael managed to finish up his investigation by way of the precious recommendations he received through your site. It’s not at all simplistic to just continually be releasing points which usually other folks may have been making money from. And we all fully understand we now have the website owner to give thanks to because of that. All of the illustrations you have made, the easy website menu, the relationships you help engender – it’s got many astounding, and it’s really facilitating our son and the family understand this matter is satisfying, which is certainly particularly essential. Many thanks for the whole thing!

发表一条评论