储存珂朵莉树#

我们用一个结构体来作为珂朵莉树的结点：

struct node {
    int l, r;
    mutable int v;
    bool operator< (const node& rhs) const {
        return this->l < rhs.l;
    }
    node(int ll, int rr, int vv) {
        l = ll, r = rr, v = vv;
    }
    node(int ll) {
        l = ll;
    }
};
set<node> s;
#define IT set<node>::iterator

这个结构体中 $l$ 和 $r$ 分别对应该结点所对应的左区间和右区间，$v$ 是当前区间的值。注意，$v$ 需要被 $\text{mutable}$ 关键字修饰，这样才能在 $s$ 中用迭代器修改。随后重载小于号，并写出两个构造函数。我们用一个储存 $\text{node}$ 的 $\text{set}$ 来储存珂朵莉树。

分裂函数#

但是，我们很容易发现：在进行查询的时候，我们不能保证查询的区间端点一定在结构体结点中，因此需要一个可以查找区间左右端点，获取到需要进行操作的区间，这便引出了下面的分裂函数：

IT split(int pos) {
    IT it = s.lower_bound(node(pos));
    if (it != s.end() && it->l == pos) {
        return it;
    }
    it--;
    int l = it->l, r = it->r, v = it->v;
    s.erase(it);
    s.insert(node(l, pos - 1, v));
    return s.insert(node(pos, r, v)).first;
}

推平函数#

如果没有推平操作的话，珂朵莉树就会退化为暴力。因此，推平操作是珂朵莉树不可或缺的一部分。

void assign(int l, int r, int v) {
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, v));
    return;
}

这段代码很好理解，首先获得左端点和右端点迭代器，**注意，一定要先获取右端点再获取左端点，否则会出错。**然后用 $\text{set}$ 的 $\text{erase}$ 函数删除从左端点到右端点内的所有结点，最后再插入进去一个对应区间的结点。由于数据是随机的，所以 $\text{assign}$ 操作会占到 $25\%$ 的情况以上。我们可以写一个随机生成数据的代码，可以发现，珂朵莉树的结点数大约到达了 $\log$ 级别，而且速度很快。

珂朵莉树的高效是由随机的 $\text{assign}$ 操作保证的。

添加函数#

十分简单，直接暴力即可。

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

注意，如果你结构体中 $v$ 并不是一个被 $\text{mutable}$ 关键字修饰的变量，那这里就会报错。

区间第 $k$ 小#

同样，先提取区间，用一个 $\text{vector}$ 存区间内所有值，然后暴力查值即可。

int kth(int l, int r, int k) {
    IT itr = split(r + 1), itl = split(l);
    vector<pair<int, int>> v; //first 存对应的值，second 存区间元素个数
    v.clear();
    for (IT it = itl;it != itr;it++) {
        v.push_back(make_pair(it->v, it->r - it->l + 1));
    }
    sort(v.begin(), v.end());
    for (int i = 0;i < v.size();i++) {
        k -= v[i].second;
        if (k <= 0) {
            return v[i].first;
        }
    }
    return -1;
}

区间幂次和#

很简单，写个快速幂暴力即可。

int qpow(int a, int b, int m) {
    int ans = 1;
    a %= m;
    while (b) {
        if (b & 1) {
            ans = (ans * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return ans;
}
int query(int l, int r, int x, int y) {
    IT itr = split(r + 1), itl = split(l);
    int res = 0;
    for (IT it = itl;it != itr;it++) {
        res = (res + (it->r - it->l + 1) * qpow(it->v, x, y)) % y;
    }
    return res;
}

总体代码#

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

#define int long long

struct node {
    int l, r;
    mutable int v;
    node(int ll, int rr, int vv) { l = ll, r = rr, v = vv; }
    node(int ll) { l = ll; }
    bool operator<(const node& rhs) const { return l < rhs.l; }
};
#define IT set<node>::iterator
set<node> s;

IT split(int pos) {
    IT it = s.lower_bound(node(pos));
    if (it != s.end() && it->l == pos) {
        return it;
    }
    it--;
    int l = it->l, r = it->r, v = it->v;
    s.erase(it);
    s.insert(node(l, pos - 1, v));
    return s.insert(node(pos, r, v)).first;
}
void assign(int l, int r, int v) {
    IT itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, v));
}
void add(int l, int r, int v) {
    IT itr = split(r + 1), itl = split(l);
    for (IT it = itl; it != itr; it++) {
        it->v += v;
    }
}
int kth(int l, int r, int k) {
    IT itr = split(r + 1), itl = split(l);
    vector<pair<int, int>> vec;
    vec.clear();
    for (IT it = itl; it != itr; it++) {
        vec.push_back(make_pair(it->v, it->r - it->l + 1));
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++) {
        k -= vec[i].second;
        if (k <= 0) {
            return vec[i].first;
        }
    }
    return -1;
}
int qpow(int a, int b, int y) {
    int res = 1;
    a %= y;
    while (b) {
        if (b & 1) {
            res = (res * a) % y;
        }
        a = (a * a) % y;
        b >>= 1;
    }
    return res;
}
int query(int l, int r, int x, int y) {
    IT itr = split(r + 1), itl = split(l);
    int res = 0;
    for (IT it = itl; it != itr; it++) {
        res = (res + (it->r - it->l + 1) * qpow(it->v, x, y)) % y;
    }
    return res;
}

int seed, n, m, vmax;
int rnd() {
    int ret = (signed)seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> seed >> vmax;
    for (int i = 1; i <= n; i++) {
        int v = (rnd() % vmax) + 1;
        s.insert(node(i, i, v));
    }
    for (int i = 1; i <= m; i++) {
        int opt = (rnd() % 4) + 1;
        int l = (rnd() % n) + 1;
        int r = (rnd() % n) + 1;
        int x, y;
        if (l > r) {
            swap(l, r);
        }
        if (opt == 3) {
            x = (rnd() % (r - l + 1)) + 1;
        } else {
            x = (rnd() % vmax) + 1;
        }
        if (opt == 4) {
            y = (rnd() % vmax) + 1;
        }

        // Comment
        if (opt == 1) {
            add(l, r, x);
        }
        if (opt == 2) {
            assign(l, r, x);
        }
        if (opt == 3) {
            cout << kth(l, r, x) << endl;
        }
        if (opt == 4) {
            cout << query(l, r, x, y) << endl;
        }
    }
    return 0;
}