rt，蒟蒻之前听别人说能用珂朵莉树的都能用平衡树，于是想使用FHQ Treap解决这个问题，结果写翻车了。

现在的主要问题可能是在split中创建新结点时会使得treap不满足堆的性质，导致遍历时无法到达所有节点（也有可能是别的原因）

大佬们能帮忙看一下嘛QWQ

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int R = 1e5 + 10, MOD = 1e9 + 7;
ll seed;
struct Node
{
	int l, r, key, len, sz, start;
	ll val;
} tree[R + 3 * R];
int tot, root;
mt19937 rd;
int crt(ll val, int len, int start)
{
	if (len == 0)
		return 0;
	tree[++tot].key = rd();
	tree[tot].val = val;
	tree[tot].sz = tree[tot].len = len;
	tree[tot].start = start;
	return tot;
}
#define lc (tree[k].l)
#define rc (tree[k].r)
void pushup(int k)
{
	tree[k].sz = tree[lc].sz + tree[rc].sz + tree[k].len;
}
void split(int k, int sz, int &x, int &y)
{
	if (k == 0)
	{
		x = y = 0;
		return;
	}
	if (sz <= tree[lc].sz)
	{
		y = k;
		split(tree[k].l, sz, x, tree[k].l);
	}
	else
	{
		sz -= tree[lc].sz;
		if (sz <= tree[k].len)
		{
			x = crt(tree[k].val, sz, tree[k].start);		// 位置<=sz的
			y = crt(tree[k].val, tree[k].len - sz, sz + 1); // 位置>sz的
		}
		else
		{
			sz -= tree[k].len;
			x = k;
			split(tree[k].r, sz, tree[k].r, y);
		}
	}
	pushup(k);
}
int merge(int x, int y)
{
	if (!x || !y)
		return x + y;
	if (tree[x].key < tree[x].key)
	{
		tree[x].r = merge(tree[x].r, y);
		pushup(x);
		return x;
	}
	else
	{
		tree[y].l = merge(x, tree[y].l);
		pushup(y);
		return y;
	}
}
int x, y, z;
void add(int l, int r, ll val)
{
}
void assign(int l, int r, ll val)
{
	split(root, l - 1, x, y);  // root按照size分为<=l和>l
	split(y, r - l + 1, y, z); // y按照size分为<=r-l+1和>r-l+1
	root = merge(merge(x, crt(val, r - l + 1, l)), z);
}
ll kth(int l, int r, int k)
{
}
ll query(int l, int r, ll x, ll mod)
{
}
ll rnd()
{
	ll res = seed;
	seed = (seed * 7 + 13) % MOD;
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, i, op, l, r;
	ll x, y, vmax;
	cin >> n >> m >> seed >> vmax;
	for (i = 1; i <= n; ++i)
	{
		root = merge(root, crt((rnd() % vmax) + 1, 1, i));
	}
	for (i = 1; i <= m; ++i)
	{
		op = (rnd() % 4) + 1;
		l = (rnd() % n) + 1;
		r = (rnd() % n) + 1;
		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);
		else if (op == 2)
			assign(l, r, x);
		else if (op == 3)
			cout << kth(l, r, x) << '\n';
		else
			cout << query(l, r, x, y) << '\n';
	}
	return 0;
}