正题

好像还没上gym所以放不了题目链接，深圳这场的题目我觉得都很好所以写个题解。

会做的都写上来了，场上很多题是队友写的，只是有参与讨论所以知道做法的题。

A 一道好题

题目大意

长度为 \(n(1\leq n\leq 1000)\) 的序列 \(a\) ，初始全为 \(0\) ，有两个操作

将第 \(x\) 个数加 \(1\) 。
将所有值为 \(x\) 的数加 \(1\) 。

要求在 \(20000\) 次操作内变成目标序列 \(b\ (b_i\leq 1000)\) 。

解题思路

考虑分治，将所有相等的数压在一起先，然后每次让后半截先 \(+1\) 然后就可以提出后半截变成子问题了。
做完后半截再做前半截。
这样大概是 \(n\log n\) 次。

D 机器人兄弟

题目大意

给一棵以 \(n\) 为根的树，\(1\sim m\) 号点是叶子，两个人从根开始轮流向叶子走，走到叶子就结束，如果一个人所在的编号为另一个人的编号 \(+1\) （模 \(m\) 意义下），则这个人胜利。

求胜负情况。

\(1\leq \sum n\leq 5\times 10^5\)

解题思路

后手一定不会输，因为可以跟着先手走，那么我们考虑什么情况下先手会输。

我们先把每个叶子向上的链一直缩到第一个有分叉的地方，保证每个叶子的父节点处一定有分叉，那么如果叶子的深度不同，那么肯定有深度浅的叶子 \(x\) 必胜深度深的叶子 \(y\) ，那么如果后手跟着先手走到了 \(y\) 父节点的深度，那么先手直接走到 \(y\) 就打平了，如果先手走到了 \(x\) ，那么先手直接在 \(y\) 的父节点处走到另一个分叉就可以了。

所以现在所有叶子深度必须相同，然后我们考虑把这些叶子向上合并，我们考虑这些叶子的父节点们，如果 \(x\) 下面的所有叶子都被 \(y\) 下面的所有叶子控制，那么我们可以直接缩减一层，否则先手走到无法被必胜的父节点处就肯定可以打平。

那么做法就很简单了，只要不同的判断是不是所有父节点都是相互必胜的就好了，如果可以就去掉叶子层，如果不可以就直接打平。

时间复杂度：\(O(n)\)

E 二合一

题目大意

给出一个长度为 \(n\) 的序列，记 \(c(l,r,x)\) 表示区间 \([l,r]\) 中 \(x\) 的数量。

求一组 \((l,r,x,y)\) 最大的

\[c(l,r,x)\ or\ c(l,r,y) \]

\(1\leq \sum n\leq 5\times 10^5\)

解题思路

我们先把区间拉到 \([1,n]\) ，然后记 \(a=c(1,n,x),b=c(1,n,y)\)

然后每次你缩减区间的时候会让 \(a=a-1\) 或者 \(b=b-1\) ，然后我们记 \(a\ and\ b\) 最高位为 \(x\) ，那么 \(a\) 和 \(b\) 肯定会有一个数字先将最高位 \(x\) 减到退位，此时 \(a\ or\ b\) 的 \(x\) 位和更低位的位置都会为 \(1\) ，而前面位的位置就等于 \(a\ or\ b\) 高于 \(x\) 位的值。