P11146

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

证法省流：视 $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)$。