CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目链接 珂朵莉树是一个可以维护区间 x 次方和查询的高效数据结构，原理十分暴力。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ChthollyTree : map<int, ll>
{
iterator split(int pos)
{
iterator it = lower_bound(pos);
if (it->first == pos)
return it;
iterator jt = it--;
return insert(jt, {pos, it->second});
}
} t;
ll n, m, seed, vmax;
ll mul(ll a, ll b, ll m) { return a * b % m; }
ll pow(ll a, ll b, ll m)
{
ll r = 1;
for (a %= m; b; a = mul(a, a, m), b >>= 1)
if (b & 1)
r = mul(r, a, m);
return r;
}
ll rnd()
{
ll ret = seed, M = 1e9 + 7;
return seed = (mul(seed, 7, M) + 13) % M, ret;
}
int main()
{
scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmax);
auto it = t.emplace(n + 1, 0).first;
for (int i = 1; i <= n; ++i)
t.emplace_hint(it, i, rnd() % vmax + 1);
for (int i = 1; i <= m; ++i)
{
int op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1;
if (l > r)
swap(l, r);
ll x = rnd() % (op == 3 ? r - l + 1 : vmax) + 1;
if (op == 1)
for_each(t.split(l), t.split(r + 1), [x](auto &p) { p.second += x; });
else if (op == 2)
t.emplace_hint(t.erase(t.split(l), t.split(r + 1)), l, x);
else
{
vector<pair<ll, int>> v;
for (auto it = t.split(l), end = t.split(r + 1); it != end;)
{
auto pre = it++;
v.emplace_back(pre->second, it->first - pre->first);
}
if (op == 3)
{
sort(v.begin(), v.end());
for (auto p : v)
if (x -= p.second, x <= 0)
{
printf("%lld\n", p.first);
break;
}
}
else
{
ll m = rnd() % vmax + 1, ans = 0;
for (auto p : v)
ans = (ans + mul(p.second, pow(p.first, x, m), m)) % m;
printf("%lld\n", ans);
}
}
}
}