颜色段均摊算法(等待重构!)

    颜色段均摊算法(等待重构!)

    十分浅显,由很多内容没有提到。有空再来填坑!

    std::set 维护颜色段

    定义颜色段(广义):放在一起具有某一性质的一段区间。

    构造

    可以考虑用一个结构体来表示一个颜色段,一个结构体记录了该颜色段的左右端点,以及该颜色段的某信息。然后将这些结构体放入 std::set 中,std::set 内部按照区间的相对顺序排序。

    下文的介绍,以维护具有相同颜色的一段区间为例。

    namespace PB {
        struct node {
            int l, r;
            mutable int c;
    
            node(int _l, int _r, int _c) : l(_l), r(_r), c(_c) {}
    
            bool operator < (const node &rhs) const {
                return l < rhs.l;
            }
        };
    
        set<node> t;
        typedef set<node>::iterator iter;
    }

    split 分裂

    有时候,对于一个颜色段,我们只需要访问它的其中一段信息即可。

    这时候就需要分裂该颜色段了。

    定义 split(x)\mathrm{split}(x) 函数:将 xx 所在的颜色段 [l,r][l, r],分裂成颜色段 [l,x−1][l, x - 1] 与颜色段 [x,r][x, r];并返回颜色段 [x,r][x, r] 在 std::set 中的位置。

    namespace PB {
        // ...
        iter split(int x) {
            if (x > n) return t.end();
    
            iter it = -- t.upper_bound((node){ x, 0, 0 });
    
            if (it->l == x) return it;
    
            int l = it->l, r = it->r, c = it->c;
            t.erase(it);
            t.insert((node){ l, x - 1, c }); return t.insert((node){ x, r, c }).first;
        }
    }

    区间操作

    有时候,对于一个序列,我们需要访问一个区间 [l,r][l, r] 的信息。

    根据分裂操作,就相当于是访问区间 [split(l),split(r+1))\left[\mathrm{split}(l), \mathrm{split}(r + 1)\right) 中颜色段的信息,依次统计即可。

    namespace PB {
        // ...
        void attend(int l, int r) {
            iter itr = split(r + 1), itl = split(l);
            for (iter it = itl; it != itr; it ++) {
                // ...
            }
        }
    }

    基于数据随机、区间推平 - 颜色段均摊算法

    当一道题目同时保证「数据随机」、「具有区间推平操作」时,大量的区间推平会使得整个序列的势能一直维持在较小的范围内。

    可以证明运用 std::set 维护颜色段的方法的时间复杂度为 O(nlog⁡log⁡n)\mathcal{O}(n \log \log n)。hqztrue 的证明。

    例题选讲

    1.【CF 896C】Willem, Chtholly and Seniorious

    CF896C

    Description

    给出一个长度为 nn 的序列 aa,你需要维护这个序列,共 mm 次操作,共 44 种操作:

    • 1 l r x:对 ∀i∈[l,r]\forall i \in[l, r],令 ai←ai+xa_i \gets a_i + x。
    • 2 l r x:对 ∀i∈[l,r]\forall i \in[l, r],令 ai←xa_i \gets x。
    • 3 l r x:求区间 [l,r][l, r] 内的第 kk 小,数字相同算多次。
    • 4 l r x y:求区间 [l,r][l, r] 内每个数字的 xx 次方模 yy 的值。

    数据范围:1≤n,m≤1051 \leq n, m \leq 10^5,1≤x,y≤1091 \leq x, y \leq 10^9。
    时空限制:2000 ms/250 MiB2000 \ \mathrm{ms} / 250 \ \mathrm{MiB}。

    Solution

    该算法起源题。

    • 操作 1:将区间 [l,r][l, r] 里所有颜色段的颜色加上 cc 即可。
    • 操作 2:将区间 [l,r][l, r] 里所有颜色段的颜色赋为 cc 即可。
    • 操作 3:访问区间 [l,r][l, r] 里的所有颜色段,提取出后排序,找到第一个前缀和 ≥k\geq k 的颜色即可。
    • 操作 4:访问区间 [l,r][l, r] 里的所有颜色段,将每个颜色段用快速幂统一统计即可。

    基于操作影响势能 or 与势能无关 - 颜色段均摊算法

    当一道题目保证「操作影响势能」或「操作与势能无关」时,则时间复杂度可以运用均摊分析法来测算。

    例题选讲

    1.【Luogu P2824】「HEOI2016/TJOI2016」排序

    Luogu P2824

    Description

    给出一个 11 至 nn 的排列,现在对这个排列序列进行 mm 次局部排序,排序分为两种:

    • 0 l r:表示将区间 [l,r][l, r] 的数升序排序。

    • 1 l r:表示将区间 [l,r][l, r] 的数降序排序。

    最后询问第 qq 位置上的数字。

    数据范围:1≤n≤1051 \leq n \leq 10^5。
    时空限制:4000 ms/256 MiB4000 \ \mathrm{ms} / 256 \ \mathrm{MiB}。

    Solution

    注意到给区间 [l,r][l, r] 内的点 升序 / 降序 排序,是赋予了一个区间有序的性质。

    可以用权值线段树来维护一个有序区间内的权值信息,然后将这些有序的区间放入 std::set 中。

    套用上述模板即可,不同点只是在于对权值线段树的处理:

    • 对于 split 操作,线段树分裂即可;
    • 对于区间排序,线段树合并即可;
    • 对于查询操作,线段树上二分即可。

    由于一次排序操作至多会进行两次线段树分裂,增加的点数是 O(log⁡n)\mathcal{O}(\log n) 的,故在整个过程中线段树的总节点个数为 O((n+m)log⁡n)\mathcal{O}((n + m) \log n) 级别的。

    在区间排序中,由于每访问一个颜色段,就会将该颜色段删去,使得势能降低。

    故总时间复杂度为 O((n+m)log⁡n)\mathcal{O}((n +m) \log n)。

    该做法支持多测 + 强制在线。