$RT$

记录

目前推测是kth或者rankx出的问题，在第一个测试点的1086行，答案是68107018，我的程序是68103608

code:

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

const int R = 5e4 + 10;
tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> t[R * 4];
int root, tot, n, a[R];
#define lc(k) (k << 1)
#define rc(k) (k << 1 | 1)
#define mid ((l + r) >> 1)
void build(int k, int l, int r)
{
	t[k].insert(make_pair(-2147483647, -1));
	t[k].insert(make_pair(2147483647, R));
	for (int i = l; i <= r; ++i)
	{
		t[k].insert(make_pair(a[i], i));
	}
	if (l == r)
	{
		return;
	}
	build(lc(k), l, mid);
	build(rc(k), mid + 1, r);
}
int rankx(int k, int l, int r, int x, int y, int val)
{
	if (x <= l && y >= r)
	{
		return t[k].order_of_key(*t[k].lower_bound(make_pair(val, 0))) - 1;
	}
	int res = 0;
	if (x <= mid)
	{
		res = rankx(lc(k), l, mid, x, y, val);
	}
	if (y > mid)
	{
		res += rankx(rc(k), mid + 1, r, x, y, val);
	}
	return res;
}
int kth(int x, int y, int k)
{
	int res = 0, l = 0, r = 1e8;
	while (l <= r)
	{
		if (rankx(1, 1, n, x, y, mid) + 1 <= k)
		{
			res = mid;
			l = mid + 1;
		}
		else
		{
			r = mid - 1;
		}
	}
	return res;
}
void update(int k, int l, int r, int pos, int val)
{
	t[k].erase(t[k].find(make_pair(a[pos], pos)));
	t[k].insert(make_pair(val, pos));
	if (l == r)
	{
		return;
	}
	if (pos <= mid)
	{
		update(lc(k), l, mid, pos, val);
	}
	else
	{
		update(rc(k), mid + 1, r, pos, val);
	}
}
int pre(int k, int l, int r, int x, int y, int val)
{
	if (x <= l && y >= r)
	{
		return (*(--t[k].lower_bound(make_pair(val, -1)))).first;
	}
	int res = -2147483647;
	if (x <= mid)
	{
		res = pre(lc(k), l, mid, x, y, val);
	}
	if (y > mid)
	{
		res = max(pre(rc(k), mid + 1, r, x, y, val), res);
	}
	return res;
}
int succ(int k, int l, int r, int x, int y, int val)
{
	if (x <= l && y >= r)
	{
		return (*(t[k].upper_bound(make_pair(val, -1)))).first;
	}
	int res = 2147483647;
	if (x <= mid)
	{
		res = succ(lc(k), l, mid, x, y, val);
	}
	if (y > mid)
	{
		res = min(succ(rc(k), mid + 1, r, x, y, val), res);
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	// freopen("P3380_1.in", "r", stdin);
	// freopen("out.out", "w", stdout);
	int m, i, l, r, k, pos;
	cin >> n >> m;
	for (i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	build(1, 1, n);
	char op;
	while (m--)
	{
		cin >> op >> l >> r;
		if (op == '1')
		{
			cin >> k;
			cout << rankx(1, 1, n, l, r, k) + 1 << '\n';
		}
		else if (op == '2')
		{
			cin >> k;
			cout << kth(l, r, k) << '\n';
		}
		else if (op == '3')
		{
			pos = l, k = r;
			update(1, 1, n, pos, k);
			a[pos] = k;
		}
		else if (op == '4')
		{
			cin >> k;
			cout << pre(1, 1, n, l, r, k) << '\n';
		}
		else
		{
			cin >> k;
			cout << succ(1, 1, n, l, r, k) << '\n';
		}
	}
	return 0;
}