【数据结构】树套树

（本部分未学完

树状数组套主席树

P2617 Dynamic Rankings

题目链接

#include <bits/stdc++.h>

using namespace std;

// #define int long long

using i64 = long long;
using i128 = __int128_t;

typedef pair<int, int> PII;

const int N = 100010;

struct Node
{
	int l, r, size;
}tr[40100000];

struct option
{
	int ll, rr, k;
}opt[N];

int n, m, idx, root[N], u;
map<int, int> uni, reuni; // uni是原值对应离散 reuni是离散后对应原值
vector<int> a(N); // 起初存储原值 后修改为离散后的值

int lowbit(int x)
{
	return x & -x;
}

int update(int pre, int l, int r, int x, int f) // 在pre的基础上 添加/删去（看f是1还是-1） 值x
{
	int now_ = ++ idx;
	tr[now_] = tr[pre];
	tr[now_].size += f;

	if (l == r) return now_; // 叶子结点
	int mid = l + r >> 1;
	if (x <= mid) tr[now_].l = update(tr[now_].l, l, mid, x, f);
	else tr[now_].r = update(tr[now_].r, mid + 1, r, x, f); 
	return now_;
}

void add(int p, int x, int f) // 在p位置 添加/删去（看f是1还是-1） 值x
{
	for (int i = p; i <= n; i += lowbit(i)) // 利用树状数组的修改方式
	{
		root[i] = update(root[i], 1, u, x, f);
	}
}

int query(vector<int> tr_l, vector<int> tr_r, int l, int r, int k) // 查询 tr_l 到 tr_r 之间的第k小数 返回编号
{
	if (l == r) return r; // 叶子结点
	int suml = 0, sumr = 0;
	for (auto &i : tr_l) suml += tr[tr[i].l].size;
	for (auto &i : tr_r) sumr += tr[tr[i].l].size;
	int mid = l + r >> 1;
	if (sumr - suml >= k) // 说明第k小数在左半部分
	{
		for (auto &i : tr_l) i = tr[i].l;
		for (auto &i : tr_r) i = tr[i].l;
		return query(tr_l, tr_r, l, mid, k);
	}
	else // 第k小数在右半部分
	{
		for (auto &i : tr_l) i = tr[i].r;
		for (auto &i : tr_r) i = tr[i].r;
		return query(tr_l, tr_r, mid + 1, r, k - sumr + suml);
	}
}

void solve()
{
    cin >> n >> m;
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		uni[a[i]] = 1;
	}
	for (int i = 1; i <= m; i ++ )
	{
		char op; cin >> op;
		if (op == 'Q') cin >> opt[i].ll >> opt[i].rr >> opt[i].k;
		else
		{
			cin >> opt[i].rr >> opt[i].k;
			uni[opt[i].k] = 1; // 离散化：记录一下哪些点被使用
		}
	}

	for (auto &i : uni)
	{
		i.second = ++ u; // 离散化：标记原值对应的离散值
		reuni[u] = i.first; // 离散化：标记老离散值对应的原值
	}
	for (int i = 1; i <= n; i ++ ) a[i] = uni[a[i]]; // 离散化：标记原值对应的离散值
	for (int i = 1; i <= m; i ++ )
		if (!opt[i].ll) opt[i].k = uni[opt[i].k]; // 离散化：标记原值对应的离散值

	for (int i = 1; i <= n; i ++ ) add(i, a[i], 1);
	for (int i = 1; i <= m; i ++ )
	{
		if (opt[i].ll)
		{
			vector<int> tr_l, tr_r;
			// 记录需要修改的部分
			for (int j = opt[i].ll - 1; j; j -= lowbit(j)) tr_l.push_back(root[j]);
			for (int j = opt[i].rr; j; j -= lowbit(j)) tr_r.push_back(root[j]);
			cout << reuni[query(tr_l, tr_r, 1, u, opt[i].k)] << '\n';
		}
		else
		{
			add(opt[i].rr, a[opt[i].rr], -1);
			add(opt[i].rr, opt[i].k, 1);
			a[opt[i].rr] = opt[i].k; // 离散化：修改原值对应的离散值
		}
	}
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t -- )
    {
        solve();
    }
}