题意
维护一个序列 \(s\)，有以下操作。
- 区间加。
- 区间覆盖。
- 求 \(l\) 到 \(r\) 的第 \(k\) 小元素。
- 求 \(l\) 到 \(r\) 的每个元素的 \(x\) 次方之和膜 \(y\)。
输入由给定种子 随机 生成。
Sol
珂朵莉树。
本质上就是拿 \(set\) 乱搞。
考虑每次操作对于颜色段的影响。
每次操作分裂出两个区间，然后暴力做就可以了。
注意要开 \(int128\)。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <set>
#define int __int128
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1e5 + 5;
namespace Mth {
int pow_(int x, int k, int p) {
int ans = 1;
while (k) {
if (k & 1) ans = ans * x % p;
x = x * x % p;
k >>= 1;
}
return ans;
}
}
namespace Chtholly {
void Mod(int &x, int y) {
if (x >= y) x -= y;
if (x < 0) x += y;
}
class Node {
public:
int l, r;
mutable int v;
Node(int _l, int _r, int _v) : l(_l), r(_r), v(_v) {}
bool operator <(const Node &t) const { return l < t.l; }
};
set <Node> Cht;
auto split(int x, int n) {
if (x > n) return Cht.end();
auto it = --Cht.upper_bound(Node(x, 0, 0));
if (it -> l == x) return it;
int l = it -> l, r = it -> r, v = it -> v;
Cht.erase(it); Cht.insert(Node(l, x - 1, v));
return Cht.insert(Node(x, r, v)).fi;
}
void assign(int l, int r, int v, int n) {
auto itr = split(r + 1, n), itl = split(l, n);
Cht.erase(itl, itr);
Cht.insert(Node(l, r, v));
}
void modify(int l, int r, int v, int n) {
auto itr = split(r + 1, n), itl = split(l, n);
for (auto it = itl; it != itr; it++)
it -> v += v;
}
int rnk(int l, int r, int k, int n) {
auto itr = split(r + 1, n), itl = split(l, n);
vector <Node> isl;
for (auto it = itl; it != itr; it++)
isl.push_back(*it);
sort(isl.begin(), isl.end(), [](Node x, Node y) { return x.v < y.v; });
int cnt = 0;
for (auto x : isl) {
cnt += x.r - x.l + 1;
if (cnt < k) continue;
return x.v;
}
return -1;
}
int query(int l, int r, int x, int y, int n) {
auto itr = split(r + 1, n), itl = split(l, n);
int ans = 0;
for (auto it = itl; it != itr; it++) {
ans += (it -> r - it -> l + 1) * (Mth::pow_(it -> v, x, y)) % y;
Mod(ans, y);
}
return ans;
}
}
array <int, N> s;
/* int rnd(int& seed) { */
/* int res = seed; */
/* seed = (seed * 7 + 13) % (int)(1e9 + 7); */
/* return res; */
/* } */
signed main() {
int n = read(), m = read(), seed = read(), maxn = read();
auto rnd = [](auto& seed) {
int res = seed;
seed = (seed * 7 + 13) % (int)(1e9 + 7);
return res;
};
for (int i = 1; i <= n; i++) {
s[i] = (rnd(seed) % maxn) + 1;
Chtholly::Cht.insert(Chtholly::Node(i, i, s[i]));
}
for (int i = 1; i <= m; i++) {
int op = (rnd(seed) % 4) + 1,
l = (rnd(seed) % n) + 1,
r = (rnd(seed) % n) + 1;
if (l > r) swap(l, r);
int x = 0, y = 0;
if (op == 3) x = (rnd(seed) % (r - l + 1)) + 1;
else x = (rnd(seed) % maxn) + 1;
if (op == 4) y = (rnd(seed) % maxn) + 1;
switch (op) {
case 1:
Chtholly::modify(l, r, x, n);
break;
case 2:
Chtholly::assign(l, r, x, n);
break;
case 3:
write(Chtholly::rnk(l, r, x, n)), puts("");
break;
default:
write(Chtholly::query(l, r, x, y, n)), puts("");
/* break; */
}
}
return 0;
}