题解代码：
```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;
}
```
本人代码:
```cpp
#include<bits/stdc++.h>
#define INF 2147483647
#define MAXN 2000000
#define MOD 998244353
#define ls son[rt][0]
#define rs son[rt][1]
#define il inline
#define rg register
using namespace std;
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' ' && __c != '\n' && __c != '\r'; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool gi (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
int val[MAXN+5],sz[MAXN+5],key[MAXN+5],son[MAXN+5][2],tot;
unsigned seed=std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);
il void pushup(int rt){sz[rt]=sz[ls]+sz[rs]+1;}
il void split(int rt,int k,int &a,int &b){
if(!rt) a=b=0;
else{
if(val[rt]<=k) a=rt,split(rs,k,rs,b);
else b=rt,split(ls,k,a,ls); pushup(rt);
}
}il int merge(int a,int b){
if(!a||!b) return a+b;
if(key[a]>key[b]){
son[a][1]=merge(son[a][1],b);
pushup(a); return a;
}else{
son[b][0]=merge(a,son[b][0]);
pushup(b); return b;
}
}int rand(){return rand_num();}
il int newnode(int v){val[++tot]=v,sz[tot]=1,key[tot]=rand(); return tot;}
il int kth(int rt,int x){
while(1){
if(x<=sz[ls]) rt=ls;
else if(x==sz[ls]+1) return val[rt];
else x-=(sz[ls]+1),rt=rs;
}
}il void ins(int &rt,int x){
int a,b; split(rt,x,a,b);
rt=merge(merge(a,newnode(x)),b);
}il void del(int &rt,int v){
int a,b,c;
split(rt,v,a,b),split(a,v-1,a,c);
c=merge(son[c][0],son[c][1]);
rt=merge(merge(a,c),b);
}il int findpre(int &rt,int v){
int a,b,p; split(rt,v-1,a,b); p=a;
if(!sz[a]){rt=merge(a,b); return -INF;}
while(son[a][1]) a=son[a][1];
rt=merge(p,b); return val[a];
}il int findnxt(int &rt,int v){
int a,b,p; split(rt,v,a,b); p=b;
if(!sz[b]){rt=merge(a,b); return INF;}
while(son[b][0]) b=son[b][0];
rt=merge(a,p); return val[b];
}il int getrank(int &rt,int v){
int a,b; split(rt,v-1,a,b);
int ret=sz[a]+1; rt=merge(a,b);
return ret;
}
#undef ls
#undef rs
int a[MAXN/10],n,Q;
struct SegmentT{
#define ls (rt<<1)
#define rs (rt<<1|1)
int root[MAXN/10];
il void build(int rt,int l,int r){
for(int i=l;i<=r;i++) ins(root[rt],a[i]);
if(l==r) return;
rg int md=(l+r)>>1;
build(ls,l,md),build(rs,md+1,r);
}il int askrank(int rt,int l,int r,int L,int R,int v){
rg int md=(l+r)>>1,ret=0;
if(L<=l&&r<=R) return getrank(root[rt],v)-1;
if(L<=md) ret+=askrank(ls,l,md,L,R,v);
if(R>md) ret+=askrank(rs,md+1,r,L,R,v);
return ret;
}il int askval(int L,int R,int k){
rg int l=0,r=1e8,ret=-1;
while(l<=r){
int md=(l+r)>>1;
if(askrank(1,1,n,L,R,md)+1<=k) ret=md,l=md+1;
else r=md-1;
}return ret;
}il void change(int rt,int l,int r,int x,int v){
del(root[rt],a[x]),ins(root[rt],v);
if(l==r) return; rg int md=(l+r)>>1;
if(x<=md) change(ls,l,md,x,v);
else change(rs,md+1,r,x,v);
}il int pre(int rt,int l,int r,int L,int R,int v){
if(L<=l&&r<=R) return findpre(root[rt],v);
rg int md=(l+r)>>1,ret=-INF;
if(L<=md) ret=max(ret,pre(ls,l,md,L,R,v));
if(R>md) ret=max(ret,pre(rs,md+1,r,L,R,v));
return ret;
}il int nxt(int rt,int l,int r,int L,int R,int v){
if(L<=l&&r<=R) return findnxt(root[rt],v);
rg int md=(l+r)>>1,ret=INF;
if(L<=md) ret=min(ret,nxt(ls,l,md,L,R,v));
if(R>md) ret=min(ret,nxt(rs,md+1,r,L,R,v));
return ret;
}
#undef ls
#undef rs
}T;
signed main(){
freopen("Tree.in","r",stdin);
freopen("Tree.out","w",stdout);
srand(time(0)); gi(n),gi(Q);
for(rg int i=1;i<=n;i++) gi(a[i]);
T.build(1,1,n);
while(Q--){
int opt=1,l,r,k; gi(opt),gi(l),gi(r);
if(opt!=3){
gi(k);
if(opt==1) printf("%d\n",T.askrank(1,1,n,l,r,k)+1);
if(opt==2) printf("%d\n",T.askval(l,r,k));
if(opt==4) printf("%d\n",T.pre(1,1,n,l,r,k));
if(opt==5) printf("%d\n",T.nxt(1,1,n,l,r,k));
}else T.change(1,1,n,l,r),a[l]=r;
}return 0;
}
```
by Yakurii @ 2021-11-16 21:16:01
@[CodyTheWolf](/user/29354)
by Yakurii @ 2021-11-16 21:16:26
@[BlackHeath](/user/439802) 所以 FHQ 到底是外层树还是内层树啊，看你表述没看懂
by DPair @ 2021-11-16 21:20:56
@[DPair](/user/66511) FHQ 是内层树啊...
by S00021 @ 2021-11-16 21:21:32
对不起表述有误，轻喷
by Yakurii @ 2021-11-16 21:22:43
@[DPair](/user/66511)
by Yakurii @ 2021-11-16 21:22:54
个人并不觉得这个做法有任何问题，我觉得应该是你自身常数比较大，或者复杂度本身就有问题不过你没分析出来而已
我看看
by DPair @ 2021-11-16 21:23:00
实测我读优+O2卡过去了）
[记录](https://www.luogu.com.cn/record/62780598)
by CodyTheWolf @ 2021-11-16 21:27:58
我也这么写的但是开O2能过啊
by 时间重洗 @ 2021-11-16 21:28:03
谢谢，可能是我哪里复杂度假掉了（（（
同样过不去dynamic rankings，
可以帮我看看哪里复杂度假了吗（）
那个能过普通平衡树和加强版
by Yakurii @ 2021-11-16 21:31:51