珂朵莉树/颜色段均摊

发表于 更新于 阅读次数： 本文字数： 3.7k 阅读时长 ≈ 7 分钟

简介

想法的本质是基于数据随机的均摊，不是数据结构

核心思想

把值相同的区间合并成一个节点保存在$set$中

结点

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node
{
    int l, r;
    mutable int v;
    Node(int a = 0, b = 0, c = 0)
    {
        l = a, r = b, v = c;
    }
    friend bool operator<(Node a, Node b)
    {
        return a.l < b.l; 
    }
};

珂朵莉树的初始化

1
std::set<Node> S;

珂朵莉树的核心操作

$split$

1
2
3
4
5
6
7
8
9
10
11
12
13
using S_IT = std::set<Node>::iterator;
S_IT split(int pos)
{
    S_IT it = S.lower_bound(Node(pos, 0, 0)); // 在set中查到左端点位置大于等于pos的结点
    if (it != S.end() && it->l == pos) // 如果这个结点的左端点恰好是pos,无需分裂直接返回
        return it;
    // 如果不是pos就一定大于pos,则包含pos的结点是上一个结点
    --it;
    ll l = it->l, r = it->r, c = it->c;
    S.erase(it);
    S.insert(Node(l, pos - 1, c));
    return S.insert((Node(pos, r, c))).first;
}

$split$操作将包含$pos$的区间$[l,r]$分裂成$[l,pos-1]$和$[pos,r]$，并返回后者的迭代器
有了$split$，任何对于$[l,r]$的区间操作
都能转换成$set$上$[split(l),split(r+1))$的操作

$assign$

1
2
3
4
5
6
7
8
9
10
11
12
using S_IT = std::set<Node>::iterator;
void assign(int l, int r, int c)
{
    S_IT it2 = split(r + 1), it1 = split(l);
    // 如果要顺便遍历区间里的信息做某些操作
    for (auto it = it1; it != it2; ++it)
    {
        // 做操作
    }
    S.erase(it1, it2);
    S.insert(Node(l, r, c));
}

$assign$用于区间赋值，同时减少$set$中结点个数
注意要先$split(r+1)$，否则可能$RE$

例题：$CF896C$

题目大意

长度为$n$的数列$a$
维护四种操作
$1\ l\ r\ x:$对于$l\leq i\leq r$置$a_i$为$a_i+x$
$2\ l\ r\ x:$对于$l\leq i\leq r$置$a_i$为$x$
$3\ l\ r\ x:$输出$a_l,a_{l+1},\cdots,a_r$这段区间里第$x$小的数
$4\ l\ r\ x\ y:$输出$(\sum_{i=l}^{r}(a_i)^x)mod\ y$

解题思路

按照模板每一种操作都很容易实现

具体代码

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
#include <bits/stdc++.h>
using ll = long long;
using PLL = std::pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 10;
ll n, m, seed, vmax;
ll a[N];
ll rnd()
{
    ll res = seed;
    seed = (seed * 7 + 13) % MOD;
    return res;
}
struct Node
{
    ll l, r;
    mutable ll v;
    Node(ll a = 0, ll b = 0, ll c = 0)
    {
        l = a, r = b, v = c;
    };
    friend bool operator<(Node a, Node b)
    {
        return a.l < b.l;
    };
};
std::set<Node> ODT;
using S_IT = std::set<Node>::iterator;
S_IT split(ll pos)
{
    auto it = ODT.lower_bound(Node(pos, 0, 0));
    if (it != ODT.end() && it->l == pos)
        return it;
    --it;
    ll l = it->l, r = it->r, v = it->v;
    ODT.erase(it);
    ODT.insert(Node(l, pos - 1, v));
    return ODT.insert(Node(pos, r, v)).first;
}
void addx(ll l, ll r, ll x)
{
    auto rit = split(r + 1), lit = split(l);
    for (auto it = lit; it != rit; ++it)
        it->v += x;
}
void modify(ll l, ll r, ll x)
{
    auto rit = split(r + 1), lit = split(l);
    ODT.erase(lit, rit);
    ODT.insert(Node(l, r, x));
}
ll x_th(ll l, ll r, ll x)
{
    auto rit = split(r + 1), lit = split(l);
    std::vector<PLL> t;
    for (auto it = lit; it != rit; ++it)
        t.push_back(PLL(it->v, it->r - it->l + 1));
    std::sort(t.begin(), t.end());
    for (ll i = 0; i < t.size(); ++i)
        if (x > t[i].second)
            x -= t[i].second;
        else
            return t[i].first;
}
ll qpow(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = (res * a) % p;
        a = (a * a) % p;
    }
    return res;
}
ll pow_sum(ll l, ll r, ll x, ll y)
{
    auto rit = split(r + 1), lit = split(l);
    ll res = 0;
    for (auto it = lit; it != rit; ++it)
        res = (res + (it->r - it->l + 1) % y * qpow(it->v, x, y) % y) % y;
    return res;
}
void solve()
{
    std::cin >> n >> m >> seed >> vmax;
    for (ll i = 1; i <= n; ++i)
    {
        a[i] = (rnd() % vmax) + 1;
        ODT.insert(Node(i, i, a[i]));
    }
    ODT.insert(Node(n + 1, n + 1, 0));
    for (ll i = 1; i <= m; ++i)
    {
        ll op, l, r, x, y;
        op = (rnd() % 4) + 1;
        l = (rnd() % n) + 1;
        r = (rnd() % n) + 1;
        if (l > r)
            std::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)
            addx(l, r, x);
        else if (op == 2)
            modify(l, r, x);
        else if (op == 3)
            std::cout << x_th(l, r, x) << '\n';
        else if (op == 4)
            std::cout << pow_sum(l, r, x, y) << '\n';
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}