$$树套树$$
$思想$
树套树是在一个数据结构中套用一个数据结构的思想,分为内外两层
外层数据结构中每一个节点都表示了一个内层数据结构
外层通常用线段树或树状数组，内层通常用平衡树或线段树
$线段树套平衡树$
#include <bits/stdc++.h>
using namespace std;
const int N = 1500010, INF = 2147483647;
int n, m;
struct Node {
int s[2], v, p;
int size;
void init(int _v, int _p)
{
v = _v, p = _p;
size = 1;
}
}tr[N];
int L[N], R[N], T[N];
int w[N], tot;
void pushup(int u)
{
tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}
void rotate(int x)
{
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}
void splay(int &root, int x, int k)
{
while (tr[x].p != k)
{
int y = tr[x].p, z = tr[y].p;
if (z != k)
(tr[y].s[1] == x) ^ (tr[z].s[1] == y) ? rotate(x) : rotate(y);
rotate(x);
}
if (!k)root = x;
}
void insert(int &root, int x)
{
int u = root, p = 0;
while (u)p = u, u = tr[u].s[x > tr[u].v];
u = ++ tot;
if (p)tr[p].s[x > tr[p].v] = u;
tr[u].init(x, p);
splay(root, u, 0);
}
int get_k(int root, int x)
{
int u = root, res = 0;
while (u)
{
if (tr[u].v < x)res += tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
else u = tr[u].s[0];
}
return res;
}
void update(int &root, int v_pre, int v_next)
{
int u = root;
while (u)
{
if (tr[u].v == v_pre)break;
if (tr[u].v < v_pre)u = tr[u].s[1];
else u = tr[u].s[0];
}
splay(root, u, 0);
int l = tr[u].s[0], r = tr[u].s[1];
while (tr[l].s[1])l = tr[l].s[1];
while (tr[r].s[0])r = tr[r].s[0];
splay(root, l, 0), splay(root, r, l);
tr[r].s[0] = 0;
pushup(r), pushup(l);
insert(root, v_next);
}
int get_pre(int root, int v)
{
int u = root, res = -INF;
while (u)
{
if (tr[u].v < v)res = max(res, tr[u].v), u = tr[u].s[1];
else u = tr[u].s[0];
}
return res;
}
int get_suc(int root, int v)
{
int u = root, res = INF;
while (u)
{
if (tr[u].v > v)res = min(res, tr[u].v), u = tr[u].s[0];
else u = tr[u].s[1];
}
return res;
}
void build(int u, int l, int r)
{
L[u] = l, R[u] = r;
insert(T[u], -INF), insert(T[u], INF);
for (int i = l; i <= r; i ++ )insert(T[u], w[i]);
if (l == r)return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int x, int v)
{
update(T[u], w[x], v);
if (L[u] == R[u])return;
int mid = L[u] + R[u] >> 1;
if (x <= mid)modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
}
int query_rank(int u, int l, int r, int x)
{
if (l <= L[u] && R[u] <= r)return get_k(T[u], x) - 1;
int mid = L[u] + R[u] >> 1, res = 0;
if (l <= mid)res += query_rank(u << 1, l, r, x);
if (r > mid)res += query_rank(u << 1 | 1, l, r, x);
return res;
}
int query_pre(int u, int l, int r, int x)
{
if (l <= L[u] && R[u] <= r)return get_pre(T[u], x);
int mid = L[u] + R[u] >> 1, res = -INF;
if (l <= mid)res = max(res, query_pre(u << 1, l, r, x));
if (r > mid)res = max(res, query_pre(u << 1 | 1, l, r, x));
return res;
}
int query_suc(int u, int l, int r, int x)
{
if (l <= L[u] && R[u] <= r)return get_suc(T[u], x);
int mid = L[u] + R[u] >> 1, res = INF;
if (l <= mid)res = min(res, query_suc(u << 1, l, r, x));
if (r > mid)res = min(res, query_suc(u << 1 | 1, l, r, x));
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )scanf("%d", &w[i]);
build(1, 1, n);
while (m -- )
{
int opt;
scanf("%d", &opt);
if (opt == 1)
{
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query_rank(1, l, r, x) + 1);
}
if (opt == 2)
{
int a, b, x;
scanf("%d%d%d", &a, &b, &x);
int l = 0, r = 1e8;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (query_rank(1, a, b, mid) + 1 <= x)l = mid;
else r = mid - 1;
}
printf("%d\n", r);
}
if (opt == 3)
{
int x, v;
scanf("%d%d", &x, &v);
modify(1, x, v);
w[x] = v;
}
if (opt == 4)
{
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query_pre(1, l, r, x));
}
if (opt == 5)
{
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query_suc(1, l, r, x));
}
}
return 0;
}
