中国珂学院

题目链接 珂朵莉树是一个可以维护区间 x 次方和查询的高效数据结构，原理十分暴力。

#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);
			}
		}
	}
}