数据结构-珂朵莉树

珂朵莉树

参考资料: 珂朵莉树/颜色段均摊 - OI Wiki

珂朵莉树（Chtholly Tree），又称ODT。源自 CF896C。

这个名称指代的是一种使用 平衡树 或 链表 维护「颜色段均摊」的技巧，而不是一种特定的数据结构。其核心思想是将指相同的一段区间合并成一个结点处理。相较于传统的线段树等数据结构，对于含有区间覆盖的操作问题，珂朵莉树可以更加方便地维护每个被覆盖区间的值。

实现（std::set）

结点类型

1
2
3
4
5
6
struct Node_t{
    int l,r;
    mutable int v; //mutable能突破 const 的限制，使变量永远可变
    Node_t(const int &il,const int &ir,const int &iv):l(il),r(ir),v(iv){} //构造函数
    bool operator<(const Node_t &o) const {return l<o.l;}
};

其中，\(v\) 为自己指定的附加数据。

结点存储

我们希望维护所有结点，使得结点代表的区间左端点单调增加且两两不交，最好可以保证所有区间的并是一个极大的连续操作。此处以 std::set<Node_t> odt；维护所有结点。显然，就需要初始化时插入区间 \([1,n]\)

split 操作

split 操作是珂朵莉树的核心。它接受一个位置 \(x\) ，将原本包含点 \(x\) 的区间（设为\([l,r]\)） 分裂为两个区间 \([l,x)\) 和 \([x,r]\) ，并返回指向后者的迭代器。

1
2
3
4
5
6
7
8
9
10
auto split(int x){
    auto it = odt.lower_bound(Node_t(x,0,0));
    if(it != odt.end() && it->l == x) return it; //刚好存在区间左端点为x,不需要分割区间
    it--;
    int l = it->l, r = it->r, v = it->v;
    odt.erase(it); //删掉原区间
    odt.insert(Node_t(l,x-1,v));
    return odt.insert(Node_t(x,r,v)).first; 
    //插入操作返回的是一个pair对象，first表示插入元素(或已存在的相同元素)的迭代器，second是bool值，表示插入是否成功
}

auto不支持的情况下，可使用对应的迭代器 set<Node_t>::iterator。

assign 操作

另外一个重要的操作：assign 。用于对一段区间进行赋值。设将要对区间 \([l,r]\) 赋值为 \(v_0\) 。

首先，将区间 \([l,r]\) 截取出来。依次调用 split(r+1),split(l) ，将此两者返回的迭代器记作 \(itr,itl\)，那么 \([itl,itr)\) 这个迭代器，就指向了珂朵莉树中 \([l,r]\) 包含的所有区间。

然后，将原有的信息删除。std::set 有成员方法 erase ，可按迭代器删除 \([first;last)\) 中的元素，即调用 odt.erase(itl，itr)；

最后，插入区间 \([l,r]\) 的新值，调用 insert() 方法即可

1
2
3
4
5
void assign(int l,int r,int v){
    auto itr = split(r+1),itl = split(l);
    odt.erase(itl,itr);
    odt.insert(Node_t(l,r,v));
}

先调用 \(split(r+1)\) 是为了防止删去 \(split(l)\) 产生的 \(l\) 为左端点的区间。

perform 操作

提取区间并进行操作，和 assign 操作类似。有时题目要求的操作可以不用到 split 时（像区间赋值就不得不用），尽量避免使用 split 转而用查找方法代替。（避免过度分割区间，但一般数据随机时无事）

1
2
3
4
5
6
void perform(int l,int r){
    auto itr = split(r+1),itl=split(l);
    for(;itl!=itr;itl++){
        //perform操作
    }
}

实现（std::map）

相较于 std::set 的实现，std::map 的实现的 split 操作写法更简单。

结点存储

由于珂朵莉树存储的区间是连续的，我们不一定要记下右端点是什么。不妨使用 map<int,int> mp; 存储所有区间，其键维护左端点，其值维护 对应的左端点到下一个左端点之前的值。

初始化时，如题目要求维护位置 \(1\) 到 \(n\) 的信息，则调用 \(mp[1] = -1\) ，\(mp[n+1]=-1\) 表示将 \([1,n+1)\) 即 \([1,n]\) 都设为特殊值 \(-1\)，\([n+1,+\infty)\) 这个区间当作哨兵使用，也可以对它进行初始化。

split 操作

参考代码：（第一份）

1
2
3
4
5
void split(int x){
    //upper_bound 是找到第一个大于x的点
    auto it = prev(mp.upper_bound(x)); //找到左端点小于等于 x 的区间 
    mp[x] = it->second;
}

参考代码：（第二份）

1
2
3
4
auto split(int x){
    auto it = prev(mp.upper_bound(x));
    return mp.insert(it,make_pair(pos,it->second)); //附上被分割区间的值
}

assign 操作

对于 assign 操作，我们需要把 \([l,r-1]\) 内所有区间左端点删除，再建立新的区间。

1
2
3
4
5
6
7
8
9
void assign(int l,int r,int v){
    split(l);
    split(r);
    auto it = mp.find(l);
    while(it->first != r){
        it = mp.erase(it);
    }
    mp[l] = v;
}

perform 操作

对于 perform 操作，和 assign 大致相同

1
2
3
4
5
6
7
8
9
void perform(int l,int r){
    split(l);
    split(r);
    auto it = mp.find(l);
    while(it->first!=r){
        //执行操作
        it = next(it);
    }
}

实现（链表）

详见珂朵莉树/颜色段均摊 - OI Wiki

关于时间复杂度

​ 显然，由于 perform 操作调用的两次 split 至多增加两个区间，而 assign 操作会删除范围的所有区间（显然包括其split操作所增加的区间），并再增加一个区间。因此，当数据随机时，复杂度才能保证正确。详见 Codeforces 上关于珂朵莉树的复杂度的证明。更详细的严格证明见 珂朵莉树的复杂度分析。证明的结论是：用 std::set 实现的珂朵莉树的复杂度为 \(O(n loglogn)\) ，而用链表实现的复杂度为 \(O(n logn)\) 。

​ 如果允许特殊构造数据，这样一定是能被卡掉的，只需要使珂朵莉树中有足够多的不同区间并反复遍历，就能使珂朵莉树的复杂度达到甚至高于平方级别。

​ 但如果存在这样的情况：元素的种类足够少，assign 操作可能使得其与相邻区间值相同，那么就可以通过一系列操作合并相同值区间，笔者做P4979 矿洞：坍塌 - 洛谷 时突发灵感。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//参考代码
//node为上文的Node_t
void merge(set<node>::iterator a){ //查看是否能合并周围结点，如果能就合并
    auto l = a,r = next(a);
    if(prev(a)->v == a->v){
        l = prev(l);
    }
    if(next(a)->v == a->v){
        r = next(r);
    }
    if(next(l) != r){
        int il = l->l,ir = prev(r)->r,iv = l->v;
        odt.erase(l,r);
        odt.insert(node(il,ir,iv));
    }
}

显然，当使用类似 assign 操作等，其末尾可使用 merge 操作。

原题AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5+10;
long long n,m,seed,vmax;
long long a[N];
struct node{
    long long l,r;
    mutable long long v;
    node(const long long &il,const long long &ir,const long long &iv):l(il),r(ir),v(iv){}; 
    bool operator <(const node &o) const {return l<o.l;}
};

set<struct node> odt;

auto split(long long x){
    auto it = odt.lower_bound(node(x,0,0));
    if(it!=odt.end()&&it->l == x) return it;
    --it;
    long long l=it->l,r=it->r,v=it->v;
    odt.erase(it);
    odt.insert(node(l,x-1,v));
    return odt.insert(node(x,r,v)).first;
}

void assign(long long l,long long r,long long v){
    auto itr=split(r+1);
    auto itl=split(l);
    odt.erase(itl,itr);
    odt.insert(node(l,r,v));
}

void add(long long l,long long r,long long v){
    auto itr=split(r+1);
    auto itl=split(l);
    for(;itl!=itr;itl++){
        itl->v += v;
    }
}


void perform1(long long l,long long r,long long x){
    auto itr = split(r+1);
    auto itl = split(l);
    vector<pair<long long,long long>> v;
    for(;itl!=itr;itl++){
        pair<long long,long long> pr;
        pr.first = itl->v;
        pr.second = itl->r - itl->l+1;
        v.push_back(pr);
    }
    sort(v.begin(),v.end());
    for(long long i=0;i<v.size();i++){
        if(x > v[i].second){
            x -= v[i].second;
        }else{
            cout << v[i].first << endl;
            break;
        }
    }
}

long long qpow(long long v,long long x,long long y){
    long long res = 1;
    while(x>0){
        if(x&1){
            res = res * v % y; 
        }
        v = v*v % y;
        x >>= 1;
    }
    return res;
}

void perform2(long long l,long long r,long long x,long long y){
    auto itr = split(r+1);
    auto itl = split(l);
    long long res = 0;
    for(;itl!=itr;itl++){
        long long l=itl->l,r=itl->r,v=itl->v;
        res += (qpow(v%y,x,y)*((r-l+1)))%y;
        res %= y;
    }
    cout << res << endl;
}

long long rnd(){
    long long ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}


int main(){
    cin >> n >> m >> seed >> vmax;
    odt.insert(node(1,n+1,0));
    for(long long i=1;i<=n;i++){
        a[i] = (rnd() % vmax) + 1;
        assign(i,i,a[i]);
    }
    

    for(long long i=1;i<=m;i++){
        long long op = (rnd() % 4) + 1;
        long long l = (rnd() % n) + 1;
        long long r = (rnd() % n) + 1;
        long long x,y;
        if (l > r)
            swap(l, r);

        if (op == 3)
            x = (rnd() % (r - l + 1)) + 1;
        else
            x = (rnd() % vmax) + 1;

        if (op == 4)
            y = (rnd() % vmax) + 1;

        if(op==1) add(l,r,x);
        else if(op==2) assign(l,r,x);   
        else if(op==3) perform1(l,r,x);
        else if(op==4) perform2(l,r,x,y);
    }
}