题解：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 来维护其他数据结构的办法有一定的作用。\ 需要用的题目先咕着。