前情提要：我的一位巨佬朋友自从学会珂朵莉树之后每天满脑子都是珂朵莉，看到什么问题就先想到珂朵莉，于是我也来学一学。

由于是自己在oiwiki上抄板子会的，所以代码有大量的相似，这篇文章讲的也很烂所以看看就好不要喷我

概述

珂朵莉树的思路其实很简单，就是维护一段段权值相同的段，这里用 set 实现。

split

既然是维护值相同的段，我们就要支持把一个段拆分开方便操作。假如我们要把包含 xx 位置的区间 [l,r][l,r] 拆成 [l,x][l, x] 和 [x+1,r][x + 1, r]，可以直接
二分出位置然后直接用 set 的特性分割就好了。

1
2
3
4
5
6
7
8
9
10
11
12
set<node>::iterator split(int x) // 分割包含位置x的区间，然后返回分割后右侧区间的迭代器
{
    auto it = chtholly.lower_bound(node(x));
    if (it != chtholly.end() && x == it -> l) { // 这种情况旧不用分割了
        return it;
    }
    it--;
    int l = it -> l, r = it -> r, val = it -> val;
    chtholly.erase(it);
    chtholly.insert(node(l, x - 1, val));
    return chtholly.insert(node(x, r, val)).first;
}

assign

如果我们一直拆，可怜的珂朵莉树就变成暴力复杂度了，所以我们还要合并。其实合并也很简单，假如我们要把 [l,r][l,r] 这段区间合并，可以分别把包含 ll 和 rr 的区间拆开，然后从左到右把 [l,r][l,r] 里的区间全删了最后再放进去修改后的区间就好了。

1
2
3
4
5
6
void merge(int l, int r, int val) // 将[l, r]所在区间合并起来，在区间外的单独被拆开
{
    auto it2 = split(r + 1), it1 = split(l); // 防止RE
    chtholly.erase(it1, it2); // 删除[it1, it2)
    chtholly.insert(node(l, r, val));
}

apply

然后就是对一段区间进行操作了。其实就是找出左右节点对应的区间然后把它们拆出来，从左到右暴力遍历修改就没了。

1
2
3
4
5
6
7
void apply(int l, int r)
{
    auto it2 = split(r + 1), it1 = split(l);
    for (auto i = it1; i != it2; i++) {
        // do sth...
    }
}

所以总体来说，珂朵莉树是一个非常好写且直观的数据结构，发明她的人很聪明，不过她的缺点也很显然，就是在非随机数据下会被卡掉。

代码实现（起源题CF896C)

这题卡longlong有点不讲理了 但是还好我写的构式代码没有被卡常数

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
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
    int l, r;
    mutable int val;
    node(int _l = -1, int _r = -1, int _val = 0) : l(_l), r(_r), val(_val) {}
    bool operator < (node other) const {
        return l < other.l;
    }
};
set<node> chtholly; // 初始插入极长区间[1, n + 1]
set<node>::iterator split(int x) // 分割包含位置x的区间，然后返回分割后右侧区间的迭代器
{
    auto it = chtholly.lower_bound(node(x));
    if (it != chtholly.end() && x == it -> l) {
        return it;
    }
    it--;
    int l = it -> l, r = it -> r, val = it -> val;
    chtholly.erase(it);
    chtholly.insert(node(l, x - 1, val));
    return chtholly.insert(node(x, r, val)).first;
}
void apply1(int l, int r, int x)
{
    auto it2 = split(r + 1), it1 = split(l);
    for (auto i = it1; i != it2; i++) {
        i -> val += x;
    }
}
void merge(int l, int r, int val) // 将[l, r]所在区间合并起来，在区间外的单独被拆开
{
    auto it2 = split(r + 1), it1 = split(l); // 防止RE
    chtholly.erase(it1, it2); // 只删除[it1, it2)
    chtholly.insert(node(l, r, val));
}
// 饭堂写的
// void apply2(int l, int r, int x)
// {
//     auto it2 = split(r + 1), it1 = split(l);
//     for (auto i = it1; i != it2; i++) {
//         i -> val = x;
//     }
// }
int apply3(int l, int r, int x)
{
    auto it2 = split(r + 1), it1 = split(l);
    vector<pair<int, int>> tp;
    for (auto i = it1; i != it2; i++) {
        tp.push_back({i -> val, i -> r - i -> l + 1});
    }
    sort(tp.begin(), tp.end(), [&](pair<int, int> x, pair<int, int> y) {
        return x.first < y.first;
    });
    for (int i = 0; i < tp.size(); i++) {
        x -= tp[i].second;
        if (x <= 0) {
            return tp[i].first;
        }
    }
}
int fastpow(int a, int b, int mod)
{
    a %= mod; // 如果你忘了，那么恭喜你看到了
    int res = 1;
    while (b) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
int apply4(int l, int r, int x, int y)
{
    int res = 0;
    auto it2 = split(r + 1), it1 = split(l);
    for (auto i = it1; i != it2; i++) {
        res = (res + ((i -> r - i -> l + 1) % y * fastpow(i -> val, x, y)) % y) % y;
    }
    return res;
}
int n, m, seed, vmax;
int rnd()
{
    int tp = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return tp;
}
signed main()
{
    cin >> n >> m >> seed >> vmax;
    chtholly.insert(node(0, n + 1));
    int ls = -1, val = -1;
    for (int i = 1; i <= n; i++) {
        int x = (rnd() % vmax) + 1;
        if (x != val) {
            if (ls != -1) {
                merge(ls, i - 1, val);
            }
            ls = i;
            val = x;
        }
    }
    merge(ls, n, val);
    for (int i = 1; i <= m; i++) {
        int ch = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1;
        if (l > r) {
            swap(l, r);
        }
        int x, y;
        if (ch == 3) {
            x = (rnd() % (r - l + 1)) + 1;
        } else {
            x = (rnd() % vmax) + 1;
        }
        if (ch == 4) {
            y = (rnd() % vmax) + 1;
        }
        if (ch == 1) {
            apply1(l, r, x);
        } else if (ch == 2) {
            merge(l, r, x);
        } else if (ch == 3) {
            cout << apply3(l, r, x) << '\n';
        } else {
            cout << apply4(l, r, x, y) << '\n';
        }
    }
    return 0;
}