0%

珂朵莉树

CF896C

真正的暴力出奇迹。

Code

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fl first
#define fr second
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 100000 + 5;

struct Node
{
LL l, r;
mutable LL v;
Node(const int &l, const int &r, const LL &v) : l(l), r(r), v(v) {}
inline bool operator < (const Node &o) const { return l < o.l; }
};

typedef set<Node>::iterator iter;

int n, m;
LL seed, vmax;
set<Node> odt;

/*
split 函数把包含 x 的区间分成 [l, x) 和 [x, r] 两部分,
并返回指向后者的迭代器

当想要对区间 [l, r] 操作时,相当于对 [split(l), split(r+1)) 进行操作
*/
iter split(LL x)
{
if (x > n) return odt.end();
iter it = --odt.upper_bound(Node{x, 0, 0});
if (it->l == x) return it;
LL 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(LL l, LL r, LL v)
{
iter itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
odt.insert(Node(l, r, v));
}

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

void Add(LL l, LL r, LL x)
{
iter itr = split(r + 1), itl = split(l);
for (; itl != itr; ++itl)
{
itl->v += x;
}
}

LL Query(LL l, LL r, LL x)
{
iter itr = split(r + 1), itl = split(l);
vector<pair<LL, LL> > v;
for (; itl != itr; ++itl) v.pb(mp(itl->v, itl->r - itl->l + 1));
sort(v.begin(), v.end());
LL now = x;
for (int i = 0; i < v.size(); i++)
{
now -= v[i].fr;
if (now <= 0) return v[i].fl;
}
}

LL qpow(LL a, LL b, LL mod)
{
a %= mod;
LL res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1) res = res * a % mod;
return res;
}

LL Query2(LL l, LL r, LL x, LL y)
{
LL res = 0;
iter itr = split(r + 1), itl = split(l);
for (; itl != itr; ++itl)
{
res = (res + qpow(itl->v, x, y) * (itl->r - itl->l + 1) % y) % y;
}
return res;
}

int main()
{
cin >> n >> m >> seed >> vmax;
for (int i = 1; i <= n; i++)
{
LL a = rnd() % vmax + 1;
odt.insert(Node{i, i, a});
}
for (int i = 1; i <= m; i++)
{
LL op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1;
LL x, y;
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);
if (op == 2) assign(l, r, x);
if (op == 3) printf("%lld\n", Query(l, r, x));
if (op == 4) printf("%lld\n", Query2(l, r, x, y));
}
return 0;
}