NOI 2025 d2t3 题解
jinqihao2023
·
·
题解
给一个 O(n+q\log^2n) 的考场做法，比标算复杂度稍劣，不过特别好写，常数没那么大，因此也可以通过。
我们先考虑暴力，奇偶分类，也就是答案为奇数做一次，偶数做一次，两个分一段。然后二分一个 mid，表示我尝试判定答案为 mid 是否正确，注意这里答案为 mid 的意思是，mid 这两个数是第一次作战摸上来的（主要是考场代码是这么写的）。
然后我们处理出两个数组，一个 l_i，一个 r_i，分别表示 i 以前的段至少需要多少次攻击牌变成防御牌，以及至多可以进行多少次攻击牌变成防御牌，l_i=\max(0,(i-mid+1)-pre1_i)，r_i=\min(r_{i-3}+1,pre0_i-(i-mid+1))（其中 pre0_i 表示 i 以前有多少个 0，pre1_i 同理），然后需要对 r 取一个后缀 \min，此时如果存在一个 i\geq mid，满足 l_i>r_i，那么就不合法了。
upd on 2025.8.25：
上面那一段中 r_i=\min(r_i,r_{i-3}+1) 实际上应该是 r_i=\min(r_i,r_{i-3}+1,r_{i-2}+1,r_{i-1}+1)，这是因为如果 r_{i-1} 或 r_{i-2} 比 r_{i-3} 小的话，那么这个时候的 r 没有及时做后缀 \min，可能导致最后更新出来的值不对。
关于充分性的补充：
我们这样最后会求出一个数组 r 满足 r_i\leq \min(r_{i+1},r_{i-3}+1,pre0_i-(i-mid+1))，那么直接根据 r 进行构造什么时候将攻击牌变成防御牌即可。
这样就得到了一个 O(qn\log n) 的暴力。
考虑优化，我们先不考虑那个烦人的 r_i=\min(r_i,r_{i-3}+1)，并且把后缀 \min 转化一下，就变成了：
化一下式子，发现其实就是 $pre0_x-(x-mid+1)+pre1_y-(y-mid+1)<0$，也就是 $pre0_x+pre1_y-x-y-2<-2mid$，所以我们相当于是选两个数，使得左式最小化。
这个东西可以直接上线段树，区间维护一个 $x$ 的最小值和 $y$ 的最小值，以及答案，合并的时候就可以计算答案了，修改是区间加，容易维护。
然后考虑加上这个 $r_i=\min(r_i,r_{i-3}+1)$ 之后咋做，可以发现，这其实就是，让上面的式子可以选 $x<y$ 的数，不过会让左式加上 $\lceil \frac{y-x}{3}\rceil$ 的额外值，因此我们线段树多维护一些量，维护 $\mod 3=i$ 的 $x,y$ 分别最小值，就可以了。
我自己写出来 3.4k 的样子，想看代码可以私信我要。
> upd on 2025.8.25：
> 实际上可以通过线段树上二分或修改一次的答案变化量 $O(1)$ 做到 $O(n+q\log n)$，然后这个上取整其实可以拆掉，复杂度就和 $3$ 无关了。