传送门 Codeforces 896C
对于区间操作类型随机且包含区间赋值操作,同时数据随机的数据结构题,可以考虑应用珂朵莉树进行求解。使用 std::set \text{std::set} std::set 实现,初始化时将各元素依次插入,时间复杂度为 O ( N log N ) O(N\log N) O(NlogN);其余操作总时间复杂度 O ( N log log N ) O(N\log\log N) O(NloglogN)。
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct node { int l, r; mutable ll v; bool operator<(const node &o) const { return l < o.l; } }; int N, M, seed, vmax; set<node> tree; set<node>::iterator split(int p) { auto it = tree.lower_bound(node{p, 0, 0}); if (it != tree.end() && it->l == p) return it; --it; int l = it->l, r = it->r; ll v = it->v; tree.erase(it); tree.insert(node{l, p, v}); return tree.insert(node{p, r, v}).first; } void assign(int l, int r, int x) { auto ed = split(r), bg = split(l); tree.erase(bg, ed); tree.insert(node{l, r, x}); } void add(int l, int r, int x) { auto ed = split(r), bg = split(l); for (auto it = bg; it != ed; ++it) it->v += x; } ll kth(int l, int r, int k) { auto ed = split(r), bg = split(l); vector<pair<ll, int>> tmp; for (auto it = bg; it != ed; ++it) tmp.push_back({it->v, it->r - it->l}); sort(tmp.begin(), tmp.end()); for (auto p : tmp) if ((k -= p.second) <= 0) return p.first; } ll pw(ll x, int n, int mod) { ll res = 1; x %= mod; while (n) { if (n & 1) res = res * x % mod; x = x * x % mod, n >>= 1; } return res; } ll sum_pw(int l, int r, int x, int m) { ll sum = 0; auto ed = split(r), bg = split(l); for (auto it = bg; it != ed; ++it) sum += pw(it->v, x, m) * (it->r - it->l); return sum % m; } int rnd() { int ret = seed; seed = ((ll)seed * 7 + 13) % 1000000007; return ret; } int main() { scanf("%d%d%d%d", &N, &M, &seed, &vmax); for (int i = 0; i < N; ++i) tree.insert(node{i, i + 1, rnd() % vmax + 1}); while (M--) { int op = rnd() % 4 + 1, l = rnd() % N + 1, r = rnd() % N + 1, x, y; if (l > r) swap(l, r); --l; if (op == 3) x = rnd() % (r - l) + 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) printf("%lld\n", kth(l, r, x)); else printf("%lld\n", sum_pw(l, r, x, y)); } return 0; }