珂朵莉树 颜色段均摊(ODT)

发表于 分类于 ， 本文字数： 1.7k 阅读时长 ≈ 6 分钟
介绍基本的珂朵莉树

珂朵莉树/颜色段均摊 ODT

set写法

结构体保存这个颜色段的 $l$,$r$,$val$. set存每一个段, 排序以 $l$ 为依据. 初始时只有一个 $1 \sim n$ 为 $0$ 的颜色段(或按照题意更改).

split 分割操作

这里 split(pos) 表示在 pos 前分割. 返回pos后面的一个颜色段.

用 lower_bound 查找大于等于 pos 的分段, 查找后判断:

  • 这个段的 $l$ 正好是 pos: 无需处理直接返回.
  • 其他情况: 此时 pos 在查找到的分段的前一个分段内, 记录前一个分段的 $l$,$r$,$val$ 并删除前一个分段, 再创建两个块, 分别是 $l \sim pos-1$ 和 $pos \sim r$, 权值不变. 然后直接返回后者的迭代器.

assign 赋值操作

这里 assign(l,r,x) 表示将 $l \sim r$ 区间的颜色块改成 x.

先分割 $l$ 和 $r+1$ , 然后设这两个分割返回的迭代器是 il 和 ir, 删除 il 到 ir-1 的全部颜色快, 注意 vector 的 erase 是 [) 区间, 所以可以直接调用 erase(il,ir). 然后再创建一个 $l \sim r$ 颜色为 x 的块.

这里有一个注意点: 要先切割 $r+1$ 再切割 $l$. 这是因为如果这两个原先就在一个块中, 分割 $l$ 后仍在一个块中, 切割 $r+1$ 时会删除原来的这个颜色块, 导致原先 $l$ 的迭代器无效.

如果先切割 $r+1$, 那么切割 $l$ 一定不会影响到 $r+1$ 的块.

例题: P3740 [HAOI2014] 贴海报

这个就是一个最基础的ODT, 按照题意操作,每一站海报就是一个颜色. 统计答案时, 把存在的每一个颜色加入一个 set 中, set 的大小即为答案. 注意判断是否有 0 的颜色, 即没被贴到的区域, 有的话答案要-1.

参考代码

完整代码

 
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
#include <iostream>
#include <set>
using namespace std;
struct node {
    int l, r;
    mutable int v;
    node(int a, int b, int c) {
        l = a;
        r = b;
        v = c;
    }
    bool operator<(const node y) const { return l < y.l; }
};
set<node> s;
auto split(int x) {
    auto it = s.lower_bound(node(x, 0, 0));
    if (it != s.end() && it->l == x) return it;
    it--;
    int l = it->l, r = it->r, v = it->v;
    s.erase(it);
    s.insert(node(l, x - 1, v));
    return s.insert(node(x, r, v)).first;
}
void assign(int l, int r, int v) {
    auto ir = split(r + 1), il = split(l);
    s.erase(il, ir);
    s.insert(node(l, r, v));
}
int main() {
    int n, m;
    cin >> n >> m;
    s.insert(node(1, n, 0));
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        assign(l, r, i);
    }
    set<int> ans;
    for (auto i = s.begin(); i != s.end(); i++) {
        ans.insert(i->v);
    }
    cout << ans.size() - ans.count(0);
    return 0;
}

map 写法

相较于 set 写法, map 稍微简单一些. 结构体的定义与 set 写法相同. 下文函数表示的含义不变.

map 的 key 对应这个颜色段的左端点 $l$, 右端点就是下一个区间的 $l-1$. value 记录这个颜色段的数据.

split 分割操作

首先我们需要找到左端点小于等于 pos 的颜色段. 考虑这样子操作: prev(mp.upper_bound(pos)). 我们便找到了这个颜色段. 找到这个颜色段的目的是获取分割后的颜色信息. 然后使 mp[pos]= 查找到的颜色即可. 由于 map 的便捷性, 我们无需返回迭代器.

assign 赋值操作

先分割 $l$ 和 $r+1$. 然后查找 $key=l$ 的键值对. 从此开始赋值, 一直向后到 $key=r+1$ 的迭代器即可.

例题: P1840 Color the Axis

依旧是一道珂朵莉树板子题, 按照题意操作即可.

参考代码

完整代码

 
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
#include <iostream>
#include <map>
using namespace std;
map<int, int> mp;
void split(int x) {
    auto it = prev(mp.upper_bound(x));
    mp[x] = it->second;
}
void assign(int l, int r, int v) {
    split(l);
    split(r + 1);
    auto it = mp.find(l);
    while (it->first != r + 1) {
        it = mp.erase(it);
    }
    mp[l] = v;
}
int main() {
    int n, m;
    cin >> n >> m;
    mp[1] = 0;
    mp[n + 1] = 0;
    while (m--) {
        int l, r;
        cin >> l >> r;
        assign(l, r, 1);

        auto it = mp.begin();
        int ans = 0;
        while (it->first != n + 1) {
            if (it->second == 0) {
                ans += next(it)->first - it->first;
            }
            it = next(it);
        }
        cout << ans << endl;
    }
    return 0;
}

链表写法

过于麻烦

例题: C. Willem, Chtholly and Seniorious

题目大意: 给你一个数列, 你需要对给定的区间 $l \sim r$ 进行如下操作:

  1. 把这些数字的加上 $x$
  2. 把这些数字设为 $x$
  3. 输出区间第 $x$ 小数
  4. 输出所有数的 $x$ 次幂之和模 $y$, 即 $\left( \sum _ {i = l} ^ r {a _ i} ^ x \right) \bmod y$

看似不好做, 但是, 由于第二个操作类型的存在, 一定存在一些相邻的数相同, 我们便可以使用珂朵莉树维护.

操作1

分割后操作即可.

操作2

直接使用 assign 操作即可.

操作3

存储这一部分区间的值和长度, 排序后便利即可.

操作4

分割后, 从左到右对区间进行计算求和即可.

注意

快速幂过程中注意开 __int128, 否则可能出现炸long long.

参考代码

完整代码

 
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
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
struct node {
    ll l, r;
    mutable ll v;
    node(ll a, ll b, ll c) {
        l = a;
        r = b;
        v = c;
    }
    bool operator<(const node y) const { return l < y.l; }
};
set<node> s;
auto split(ll x) {
    auto it = s.lower_bound(node(x, 0, 0));
    if (it != s.end() && it->l == x) return it;
    it--;
    ll l = it->l, r = it->r, v = it->v;
    s.erase(it);
    s.insert(node(l, x - 1, v));
    return s.insert(node(x, r, v)).first;
}
void assign(ll l, ll r, ll v) {
    auto ir = split(r + 1), il = split(l);
    s.erase(il, ir);
    s.insert(node(l, r, v));
}
ll n, m, sed, vmax;
ll rnd() {
    ll ret = sed;
    sed = ((ll)sed * 7 + 13) % 1000000007;
    return ret;
}
ll a[100005];
void s1(ll l, ll r, ll x) {
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl++) {
        itl->v += x;
    }
}
void s2(ll l, ll r, ll x) { assign(l, r, x); }
void s3(ll l, ll r, ll x) {
    vector<pair<ll, ll>> ve;
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl++) {
        ve.push_back(make_pair(itl->v, itl->r - itl->l + 1));
    }
    sort(ve.begin(), ve.end());
    ll cnt = 0;
    for (auto i : ve) {
        if (cnt + i.second >= x) {
            cout << i.first << endl;
            return;
        }
        cnt += i.second;
    }
}
ll fpow(ll x, ll y, ll p) {
    ll res = 1;
    while (y) {
        if (y & 1) res = (__int128)res * x % p;
        x = (__int128)x * x % p;
        y >>= 1;
    }
    return res;
}
void s4(ll l, ll r, ll x, ll y) {
    auto itr = split(r + 1), itl = split(l);
    ll ans = 0;
    for (; itl != itr; itl++) {
        ans += fpow(itl->v, x, y) * (itl->r - itl->l + 1) % y;
        ans %= y;
    }
    cout << ans << endl;
}
int main() {
    cin >> n >> m >> sed >> vmax;
    for (ll i = 1; i <= n; i++) {
        a[i] = rnd() % vmax + 1;
    }
    s.insert(node(1, n, 0));
    ll lat = 1;
    for (ll i = 2; i <= n; i++) {
        if (a[i] != a[i - 1]) {
            assign(lat, i - 1, a[i - 1]);
            lat = i;
        }
    }
    assign(lat, n, a[n]);
    for (ll i = 1; i <= m; i++) {
        ll op, l, r, x;
        op = (rnd() % 4) + 1;
        l = (rnd() % n) + 1;
        r = (rnd() % n) + 1;
        if (r < l) swap(l, r);
        if (op == 3) {
            x = (rnd() % (r - l + 1)) + 1;
            s3(l, r, x);
        } else {
            x = (rnd() % vmax) + 1;
            if (op == 1) {
                s1(l, r, x);
            } else if (op == 2) {
                s2(l, r, x);
            }
        }
        if (op == 4) {
            ll y = (rnd() % vmax) + 1;
            s4(l, r, x, y);
        }
    }
}

习题