AT_abc435_e [ABC435E] Cover query 题解
题目链接（洛谷）
题目大意
有 \(N\) 个格子，初始全为白色。先有 \(Q\) 次区间染色操作，每次把区间 \([l,r]\) 的格子染成黑色，问每次操作后有多少个格子任然是白色。
\(1 \le N \le 10^9,1\le Q \le 2 \times 10^5\)
做法
看到区间推平，容易想到 ODT。
赛时看到本题的操作只有区间推平，于是就写了用 set 维护连续的黑色段。
先贴一下核心代码。
//ss 是一个维护结构体 range(区间)的 set，range 基于 r 比较
while(q--){int l,r;read(l),read(r);auto t=ss.lower_bound(range{l,l});//找到第一个会被删除的区间#define y (*t)for(;t!=ss.end();){if(y.l>r) break;cmin(l,y.l);cmax(r,y.r);//这两行的作用可以画个图，即两区间相交，最后的黑色的范围是两个区间并起来。ans+=y.r-y.l+1;//维护答案t=ss.erase(t);//erase 的返回值是下一个元素}ans-=r-l+1;ss.insert(t,{l,r});printf("%d\n",ans);
}
我们来尝试证明这个做法的复杂度。定义势能函数 \(\phi\) 为黑色段的数量，即 ss.size()。每次插入操作最多使 \(\phi\) 加一，且 \(\phi \ge 0\)，所以势能的总变化量是 \(O(Q)\)，即我们会调用 \(O(Q)\) 次 inesrt 或 erase。而在 set 根据迭代器插入或删除都是 \(O(1)\) 的，故维护 set 的总复杂度为 \(O(Q)\)。复杂度瓶颈在于每次查询时找区间的 lower_bound，整个代码复杂度为 \(O(Q \log Q)\)。
不知道这算不算 ODT。完整代码可以在 AC 记录查看。
此外，本题显然存在 \(O(Q \log N)\) 的动态开点线段树做法，这里不做介绍。
拓展
介绍一个颜色段均摊理论的小应用。
如果本题加强为求区间 \([l,r]\) 的白色的格子数目，那么 ODT 查询时就复杂度不对了。此时只能写线段树。
假如你不会用线段树区间推平，只会区间加。应该没有这样的人吧。我们也可以用颜色段均摊理论将区间推平转化为区间加。
具体做法为用 set 维护区间白色连续段，对于在区间中的白色的连续段，在 set 中删除，在线段树上区间加。
该做法在此题可能没有什么价值，但有些题目的性质可能没有这么好，这种用 ODT 来维护其他数据结构的办法有一定的作用。
需要用的题目有 P4690 [Ynoi Easy Round 2016] 镜中的昆虫，P5524 [Ynoi2012] NOIP2015 充满了希望