P11146

Carnival · 2025-09-18 22:56:38 · 题解

题解省流：做法同喵仔牛奶等人。题解区最后几篇都是这个做法，但全部没有证明复杂度，同时讨论区也有人不理解为什么复杂度是对的。本篇题解意在补充复杂度证明，不会侧重于做法的复述，如果想知道这个做法的实现细节可以看那几篇题解。

证法省流：视 n,m 同阶，时间复杂度 \mathcal{O}(n \log n)，势能分析。其实不是很难证？

简单复述做法：先删去 a_i=b_i 的位置，从左到右贪心，如果当前位是 l 且 a_l=0，不妨设以当前位为左端点有 k 个不同的区间，分别为 [l,r_1],[l,r_2],\cdots,[l,r_k]，我们的策略是选取 [l,r_1] 进行区间取反（可以简单通过异或差分实现故不是复杂度瓶颈），并将剩余区间改为 [r_1+1,r_2],[r_2+1,r_3],\cdots,[r_{k-1}+1,r_k]，如果与已有的区间重复则只保留一个。

正确性不难证明：不妨把 [l,r_1],[r_1+1,r_2],[r_2+1,r_3],\cdots,[r_{k-1}+1,r_k] 每个区间的长度都缩成一，那么得到 [1,1],[2,2],\cdots,[k,k]，同时 [l,r_1],[l,r_2],\cdots,[l,r_k] 变成了 [1,1],[1,2],[1,3],\cdots,[1,k]，显然前面一组区间可以实现 k 个数任意取反，只需证明后面一组区间也可实现，这个用数学归纳法很好证明。

考虑复杂度证明：定义区间 [l,r] 的势能为 \log_2(r-l+2)。初始态势能是 \mathcal{O}(n \log n) 量级的，而终点态势能 \ge 0。考虑每次修改前的第 i( i \ge 2) 个区间为 [l,r_i]，改后变为了 [r_{i-1}+1,r_i]，作差得势能减少了 \log_2(1+\frac{r_{i-1}-l+1}{r_i-r_{i-1}+1})。那么，对于两对相邻区间 [l,r_{i-1}] 与 [l,r_i]，如果 r_{i-1}-l+1 \ge r_i-r_{i-1}+1 那么势能至少减少一，因此对这样的区间对进行操作的次数不会超过势能的量级 \mathcal{O}(n \log n)；否则第 i 个区间长度至少为第 i-1 个区间长度的两倍：考虑有 r_{i-1}-l < r_i-r_{i-1}，则 r_i-l+1=(r_i-r_{i-1})+(r_{i-1}-l+1) \ge 2(r_{i-1}-l+1)。对于相同的 l，由于区间长度每次会乘以二，这样的区间对不会超过 \log n 个，那么由于 l \in [1,n]，这样的区间对不会超过 n \log n 个，同样只会对这样的区间对操作 \mathcal{O}(n \log n) 次，总时间复杂度 \mathcal{O}(n \log n)。