珂朵莉树

模版

C++
template<class K, class V>
struct ODT {
    map<K, V> odt;
    ODT(K mx) {
        odt[mx + 1] = V();
    } 
    void split(K x) {
        auto it = prev(odt.upper_bound(x));
        odt[x] = it -> second;
    }
    void assign(K L, K R, V val) { // 区间赋值
        R++;
        split(L); split(R);
        auto it = odt.find(L);
        while (it -> first != R) {
            it = odt.erase(it);
        }
        odt[L] = val;
    }
    void update(K L, K R) { // 区间更新
        R++;
        split(L); split(R);
        auto it = odt.find(L);
        while (it -> first != R) {
            K l = it -> first; // 区间左端点
            K r = next(it) -> first - 1; // 区间右端点
            V v = it -> second; // 区间值
            // Do what you want to do
            it = next(it);
        }
    }
    V& operator[](K x) {
        return odt[x];
    }
}; // ODT
// 基于 map 实现的珂朵莉树
// K 代表区间类型, int 或 long long
// V 代表存的值

例题

CF896CCF817F

Problem - C - Codeforces

操作一, 区间加

操作二, 区间赋值

操作三, 输出区间第k大

操作四, 输出区间x次幂的和模y

代码

C++
#include <bits/stdc++.h>
using namespace std;

// 2024 OneWan

long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
template<class K, class V>
struct ODT {
    map<K, V> odt;
    ODT(K mx) {
        odt[mx + 1] = V();
    } 
    void split(K x) {
        auto it = prev(odt.upper_bound(x));
        odt[x] = it -> second;
    }
    void assign(K L, K R, V val) { // 区间赋值
        R++;
        split(L); split(R);
        auto it = odt.find(L);
        while (it -> first != R) {
            it = odt.erase(it);
        }
        odt[L] = val;
    }
    void add(K L, K R, V val) { // 区间加
        R++;
        split(L); split(R);
        auto it = odt.find(L);
        while (it -> first != R) {
            K l = it -> first; // 区间左端点
            K r = next(it) -> first - 1; // 区间右端点
            V &v = it -> second; // 区间值
            v += val;
            it = next(it);
        }
    }
    V kth(K L, K R, K rk) { // 区间第k大
        R++;
        split(L); split(R);
        auto it = odt.find(L);
        vector<pair<V, K>> res;
        while (it -> first != R) {
            K l = it -> first; // 区间左端点
            K r = next(it) -> first - 1; // 区间右端点
            V v = it -> second; // 区间值
            res.push_back({v, r - l + 1});
            it = next(it);
        }
        sort(begin(res), end(res));
        for (auto &[x, y] : res) {
            rk -= y;
            if (rk <= 0) return x;
        }
        return -1;
    }
    V query(K L, K R, V x, V mod) { // 区间更新
        R++;
        split(L); split(R);
        auto it = odt.find(L);
        V res = 0;
        while (it -> first != R) {
            K l = it -> first; // 区间左端点
            K r = next(it) -> first - 1; // 区间右端点
            V v = it -> second; // 区间值
            res = (res + qpow(v % mod, x, mod) * (r - l + 1) % mod) % mod;
            it = next(it);
        }
        return res;
    }
    V& operator[](K x) {
        return odt[x];
    }
}; // ODT
int seed;
int rnd() {
    int res = seed;
    seed = (1LL * seed * 7 + 13) % 1000000007;
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, vmax;
    cin >> n >> m >> seed >> vmax;
    ODT<int, long long> odt(n);
    for (int i = 1 ; i <= n ; i++) {
        int a = rnd() % vmax + 1;
        odt[i] = a;
    }
    for (int i = 1 ; i <= m ; i++) {
        int op, L, R, x, y;
        op = rnd() % 4 + 1;
        L = rnd() % n + 1;
        R = rnd() % n + 1;
        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) {
            odt.add(L, R, x);
        } else if (op == 2) {
            odt.assign(L, R, x);
        } else if (op == 3) {
            cout << odt.kth(L, R, x) << "\n";
        } else if (op == 4) {
            cout << odt.query(L, R, x, y) << "\n";
        }
    }
    return 0;
}

Problem - F - Codeforces

操作一, 添加区间

操作二, 删除区间

操作三, 反转区间, 存在的删除, 不存在的添加

代码

C++
template<class K, class V>
struct ODT {
    map<K, V> odt;
    ODT(K mx) {
        odt[mx + 1] = V();
    } 
    void split(K x) {
        auto it = prev(odt.upper_bound(x));
        odt[x] = it -> second;
    }
    void assign(K L, K R, V val) { // 区间赋值
        R++;
        split(L); split(R);
        auto it = odt.find(L);
        while (it -> first != R) {
            it = odt.erase(it);
        }
        odt[L] = val;
    }
    void reverse(K L, K R) { // 区间反转
        R++;
        split(L); split(R);
        auto it = odt.find(L);
        while (it -> first != R) {
            K l = it -> first; // 区间左端点
            K r = next(it) -> first - 1; // 区间右端点
            V &v = it -> second; // 区间值
            v ^= 1;
            it = next(it);
        }
    }
    K query() { // 查询
        for (auto &[x, y] : odt) {
            if (y == 0) {
                return x;
            }
        }
        return -1;
    }
    V& operator[](K x) {
        return odt[x];
    }
}; // ODT
// 基于 map 实现的珂朵莉树
// K 代表区间类型, int 或 long long
// V 代表存的值
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ODT<long long, int> odt(1000000000000000000LL);
    odt.assign(1LL, 1000000000000000000LL, 0);
    int n;
    cin >> n;
    for (int i = 0 ; i < n ; i++) {
        int op;
        long long L, R;
        cin >> op >> L >> R;
        if (op == 1) {
            odt.assign(L, R, 1);
        } else if (op == 2) {
            odt.assign(L, R, 0);
        } else if (op == 3) {
            odt.reverse(L, R);
        }
        cout << odt.query() << "\n";
    }
    return 0;
}