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
| struct Ele {
int l, r;
mutable int v;
inline bool operator<(const Ele sec) const {
return l < sec.l;
}
};
inline bool cmpv(Ele fir, Ele sec) {
return fir.v < sec.v;
}
set<Ele> odt;
inline auto Split(int p) {
if (p > n) return end(odt);
auto pit = --odt.upper_bound(Ele{l: p, r: -1, v: -1});
int l = pit->l, r = pit->r, v = pit->v;
odt.erase(pit);
if (l < p) odt.insert(Ele{l: l, r: p - 1, v: v});
return odt.insert(Ele{l: p, r: r, v: v}).first;
}
void modifySecAdd(int l, int r, int v) {
auto rit = Split(r + 1), lit = Split(l);
for (auto i = lit; i != rit; ++i) {
i->v += v;
}
}
void modifySecAss(int l, int r, int v) {
auto rit = Split(r + 1), lit = Split(l);
odt.erase(lit, rit);
odt.insert(Ele{l: l, r: r, v: v});
}
int cntinsec; Ele insec[MAXn + 10];
int RanktoVal(int l, int r, int rk) {
auto rit = Split(r + 1), lit = Split(l);
cntinsec = 0;
for (auto i = lit; i != rit; ++i) {
insec[++cntinsec] = *i;
}
sort(insec + 1, insec + 1 + cntinsec, cmpv);
for (int i = 1; i <= cntinsec; ++i) {
int len = insec[i].r - insec[i].l + 1;
if (rk <= len) return insec[i].v;
else rk -= len;
}
return -1;
}
int queryPowersum(int l, int r, int y, int mod) {
auto rit = Split(r + 1), lit = Split(l);
int ans = 0;
for (auto i = lit; i != rit; ++i) {
ans = addmod(ans + (i->r - i->l + 1) * power(i->v % mod, y, mod) % mod, mod);
}
return ans;
}
signed main() {
for (int i = 1; i <= n; ++i) {
odt.insert(Ele{l: i, r: i, v: a[i]});
}
for (int i = 1, opt, l, r, x, y; i <= m; ++i) {
if (opt == 1) {
modifySecAdd(l, r, x);
} else if (opt == 2) {
modifySecAss(l, r, x);
} else if (opt == 3) {
printf("%lld\n", RanktoVal(l, r, x));
} else {
printf("%lld\n", queryPowersum(l, r, x, y));
}
}
return 0;
}
|
