题解 P3380 【【模板】二逼平衡树（树套树）】
CodyTheWolf
2018-11-18 21:29:54
### [开头小广告：自己做的一个模板库OwO](https://www.luogu.org/blog/29354/Templet)
------------
## 提供一份无指针线段树套FHQ Treap的代码
上面的模板库有我的FHQ Treap的板子，如果和您的风格不一样可以看一下
大体思路就不用多说了，跟其他线段树套平衡树的操作是一样的。
此题解就给那些无指针的FHQ Treap党参考，对拍使用吧
注意：不开O2会T一个点（#9），请自行卡常通过或者开O2 qwq
------------
# Code
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 5e4 + 5, MAXM = 1e7;
const int INF = 0x7fffffff;
int a[MAXN];
int n, m;
int val[MAXM], sz[MAXM], heap[MAXM], l[MAXM], r[MAXM];
int tot;
struct FHQ_Treap
{
int root;
inline void Update(int x)
{
sz[x] = sz[l[x]] + sz[r[x]] + 1;
return;
}
inline int Merge(int x, int y)
{
if (!x || !y)
return x + y;
if (heap[x] < heap[y])
return r[x] = Merge(r[x], y), Update(x), x;
return l[y] = Merge(x, l[y]), Update(y), y;
}
inline void Split(int x, int key, int &u, int &v)
{
if (!x)
{
u = v = 0;
return;
}
if (val[x] <= key)
u = x, Split(r[x], key, r[u], v);
else
v = x, Split(l[x], key, u, l[v]);
Update(x);
return;
}
inline int Create(int key)
{
val[++tot] = key, heap[tot] = rand(), sz[tot] = 1;
return tot;
}
int x, y, z;
inline void Insert(int key)
{
Split(root, key, x, y);
root = Merge(x, Merge(Create(key), y));
return;
}
inline void Delete(int key)
{
Split(root, key, x, z);
Split(x, key - 1, x, y);
y = Merge(l[y], r[y]);
root = Merge(x, Merge(y, z));
return;
}
inline int FindRank(int key)
{
Split(root, key - 1, x, y);
int ans = sz[x] + 1;
root = Merge(x, y);
return ans;
}
inline void Build(int l, int r)
{
for (int i = l; i <= r; i++)
Insert(a[i]);
return;
}
inline int FindKey(int x, int rak)
{
if (rak <= sz[l[x]])
return FindKey(l[x], rak);
if (rak == sz[l[x]] + 1)
return val[x];
return FindKey(r[x], rak - sz[l[x]] - 1);
}
inline int Lower(int key)
{
Split(root, key - 1, x, y);
int ans;
if (sz[x])
ans = FindKey(x, sz[x]);
else
ans = -INF;
root = Merge(x, y);
return ans;
}
inline int Upper(int key)
{
Split(root, key, x, y);
int ans;
if (sz[y])
ans = FindKey(y, 1);
else
ans = INF;
root = Merge(x, y);
return ans;
}
} FT[MAXN << 2];
#define mid ((x + y) >> 1)
#define lson (pst << 1)
#define rson (pst << 1 | 1)
struct SegmentTree
{
int root[MAXN << 2];
inline void Build(int x, int y, int pst)
{
FT[pst].Build(x, y);
if (x != y)
Build(x, mid, lson), Build(mid + 1, y, rson);
return;
}
inline int QueryRank(int x, int y, int pst, int l, int r, int key)
{
if (y < l || x > r)
return 0;
if (l <= x && y <= r)
return FT[pst].FindRank(key) - 1;
return QueryRank(x, mid, lson, l, r, key) + QueryRank(mid + 1, y, rson, l, r, key);
}
inline int QueryKey(int l, int r, int rak)
{
int x = 0, y = 1e8, ans = -1;
while (x <= y)
{
if (QueryRank(1, n, 1, l, r, mid) + 1 <= rak)
ans = mid, x = mid + 1;
else
y = mid - 1;
}
return ans;
}
inline void Update(int x, int y, int pst, int p, int k)
{
FT[pst].Delete(a[p]);
FT[pst].Insert(k);
if (x != y)
{
if (p <= mid)
Update(x, mid, lson, p, k);
else
Update(mid + 1, y, rson, p, k);
}
return;
}
inline int Lower(int x, int y, int pst, int l, int r, int k)
{
if (y < l || x > r)
return -INF;
if (l <= x && y <= r)
return FT[pst].Lower(k);
return max(Lower(x, mid, lson, l, r, k), Lower(mid + 1, y, rson, l, r, k));
}
inline int Upper(int x, int y, int pst, int l, int r, int k)
{
if (y < l || x > r)
return INF;
if (l <= x && y <= r)
return FT[pst].Upper(k);
return min(Upper(x, mid, lson, l, r, k), Upper(mid + 1, y, rson, l, r, k));
}
} ST;
signed main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
ST.Build(1, n, 1);
for (int i = 1, opt, l, r, p, k; i <= m; i++)
{
scanf("%d", &opt);
if (opt == 1)
{
scanf("%d %d %d", &l, &r, &k);
printf("%d\n", ST.QueryRank(1, n, 1, l, r, k) + 1);
}
if (opt == 2)
{
scanf("%d %d %d", &l, &r, &k);
printf("%d\n", ST.QueryKey(l, r, k));
}
if (opt == 3)
{
scanf("%d %d", &p, &k);
ST.Update(1, n, 1, p, k);
a[p] = k;
}
if (opt == 4)
{
scanf("%d %d %d", &l, &r, &k);
printf("%d\n", ST.Lower(1, n, 1, l, r, k));
}
if (opt == 5)
{
scanf("%d %d %d", &l, &r, &k);
printf("%d\n", ST.Upper(1, n, 1, l, r, k));
}
}
return 0;
}
```