CF896C Willem, Chtholly and Seniorious 题解 珂朵莉树 模板题

题目链接：https://codeforces.com/problemset/problem/896/C

解题思路：完全来自 oi.wiki

示例程序：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;

struct Node {
    int l, r;
    mutable ll v;

    Node(int l, int r = -1, ll v = 0) : l(l), r(r), v(v) {}

    bool operator < (const Node &b) const {
        return l < b.l;
    }
};

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound(Node(x));
    if (it != odt.end() && it->l == x) return it;

    it--;
    if (it->r < x) return odt.end();

    int l = it->l, r = it->r;
    ll v = it->v;

    odt.erase(it);
    odt.insert(Node(l, x-1, v));
    return odt.insert(Node(x, r, v)).first;
}

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

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

ll get_kth(int l, int r, int k) {
    auto itr = split(r+1);
    auto itl = split(l);
    vector<Node> vec(itl, itr);
    sort(vec.begin(), vec.end(), [](auto a, auto b) {
        return a.v < b.v;
    });
    for (auto &[l, r, v] : vec) {
        k -= r - l + 1;
        if (k <= 0)
            return v;
    }
    return -1;
}

ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    for (ll t = a % p; b; b >>= 1, t = t * t % p)
        if (b & 1ll)
            (res *= t) %= p;
    return res;
}

ll get_sum(int l, int r, int k, int p) {
    auto itr = split(r+1);
    auto itl = split(l);
    ll res = 0;
    for (auto it = itl; it != itr; it++) {
        auto [l, r, v] = *it;
        res += (r - l + 1) * qpow(v, k, p);
        res %= p;
    }
    return res;
}

int n, m;
ll a[maxn], seed, Vmax;

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

int main() {
    scanf("%d%d%lld%lld", &n, &m, &seed, &Vmax);
    for (int i = 1; i <= n; i++) {
        a[i] = rnd() % Vmax + 1;
        odt.insert(Node(i, i, a[i]));
    }
    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) {
            add(l, r, x);
        }
        else if (op == 2) {
            assign(l, r, x);
        }
        else if (op == 3) {
            ll ans = get_kth(l, r, x);
            printf("%lld\n", ans);
        }
        else { // op == 4
            ll ans = get_sum(l, r, x, y);
            printf("%lld\n", ans);
        }
    }

    return 0;
}

注意点：

1. Node 的成员变量 v 前必须加 mutable。因为 std::set 中的元素默认是不可修改的（const），加上 mutable 允许我们在不破坏 set 排序（以 l 排序）的前提下，直接修改 v 的值。