CF2157E Adjusting Drones
发现对于一次变化，如果值 \(i\) 和 \(i+1\) 均满足 \(cnt_{i},cnt_{i+1} \ge 1\)，那么 \(i\) 相当于是直接平移到 \(i+1\)。因为 \(cnt_i-1 +1=cnt_i\)。如果 \(cnt_{i+1}=0\)，那么相当于 \(cnt_i-1\) 平移到 \(i+1\)。
考虑维护一个联通块的代价，不同联通块互不影响。维护 \([1,i]\) 的答案，假定 \([i+1,2n]\) 的 \(cnt\) 均为 \(0\)。加入 \(i\)，若之前操作的过程中有一个值平移到 \(i\) 之后，那么实际上在平移到 \(i\) 时 \(cnt\) 就不会减了，而需要等到 \(cnt_i\) 减到 \(0\) 才能继续减。也就是说，之前的终止位置 \(r\) 现在实际上是 \(r+cnt_i\)。如果之前操作的过程中不存在平移到 \(i\) 的情况，也就是终止位置 \(r<i\)，说明 \(i\) 开始就是一个新的联通块，此时在假定后面都是 \(0\) 的情况下终止位置为 \(i+(cnt_i-k)\)。
显然，一定能够得到某个时刻的起始位置和终止位置的距离恰好是最终答案，且中途的距离不会超过答案。时间复杂度 \(O(n)\)。
CF2157F Git Gud
直观地，我们可以尝试对 \([1,n]\) 分块，让每个块内的值先达到块的右端点，然后再通过不断从当前块的右端点跳到下一个块的右端点实现所有值均不小于 \(n\)。因为在不管额外的 \(1000\) 的代价时，这样只会有 \(O(\frac{n}{B})\) 次大跳，其它的 \(O(n)\) 次都是 \(l=1\) 的小跳。
假设 \(n=8\)，将 \([1,n]\) 分成了 \(1234|5678\)。显然我们需要尽可能地让 \(y_i < y_{i-1}\)，而又不破坏每个块内元素的相对顺序。因为 \([1234]\) 和 \([5678]\) 是独立的，所以可以构造形如：\(516273\) 的顺序，这样 \(y_i > y_{i-1}\) 的情况只会有 \(O(B)\) 个，且保证的块内的相对顺序。那么总的代价就是 \(n+\frac{n}{B}\times (B+1000) +B \times 1000\)。也就是 \(2n+1000(\frac{n}{B}+B)\) 的。在 \(B=\sqrt{n}\) 时大概是 \(1.5 \times 10^6\)。已经很接近了。
既然可以将 \([1,n]\) 分成 \(O(\frac{n}{B})\) 个块，那么能不能再分呢。也就是说，对于块内点先跳到右端点的问题，实际上可以看做一个 \([1,B]\) 的子问题。记二次分块的块长为 \(B2\)。仿照上面的操作，将 \(O(\frac{n}{B2})\) 个小块依次处理，且保证内部相对顺序，可以在 \(n+B2 \times 1000\) 的代价内将小块内部的点先移动到右端点。那么此时相当于一个大块内只有 \(O(\frac{B}{B2})\) 个点了。再次移动代价为 \(n+\frac{B}{B2}1000\)。此时剩下 \(O(\frac{n}{B})\) 个点，代价 \(n+\frac{n}{B}1000\)。那么总的代价就是 \(3n+1000(\frac{n}{B}+\frac{B}{B2}+B2)\)。在 \(B=n^{\frac{2}{3}},B2=n^{\frac{1}{3}}\) 时代价降至 \(3n+3000 n^{\frac{1}{3}}\)。远小于 \(10^6\)。
CF2157G Isaac's Queries
显然在 \(\frac{n\times(n+1)}{2}\) 次询问后可以知道所有询问的答案……
尝试通过已知信息得到其它未知信息。由 \(f(l,r)=f(x,l-1)\oplus f(x,r)\) 得知，在 \(Q(x,l-1)\ne Q(x,r)\) 时，\(Q(l,r)=\max(Q(x,l-1),Q(x,r))\)。因为两个询问中 \(highbit\) 大的一定在 \([l,r]\) 出现了奇数次，且更高为一定出现偶数次。
也就说，只要对于一个 \(x\)，知道了 \(Q(x,l),Q(x,r)\) 且 \(Q(x,l)\ne Q(x,r)\)，就可以推出 \(Q(l+1,r)\)。贪心地，从 \(l-x+1\) 最大的开始，如果当前询问不知道，就询问一次，然后推出所有可以知道的询问。这样的代价在数据随机的情况下并不大。