板子题
需要卡常
#include <bits/stdc++.h>
#define ls(q) tr[q].ls
#define rs(q) tr[q].rs
#define pc(c) putchar(c)
#define rep(a,b,c) for (int (a) = (b) ; (a) < (c) ; ++(a))
using namespace std;
using ll = long long ;
using pii = pair<int,int> ;
const int maxn = 5e4 + 10,inf = 2147483647;
int root[maxn << 2],a[maxn],idx,n;
struct node {
int ls,rs,val,sz,key ;
}tr[maxn * 40];
mt19937 rnd(233);
inline void pushup(int q){
tr[q].sz = tr[ls(q)].sz + tr[rs(q)].sz + 1;
}
inline int mknode(int x){
tr[++idx] = {0,0,x,1,int(rnd())};
return idx ;
}
inline void split(int q,int v,int &l,int &r){
if (!q) {l = r = 0 ; return ;}
if (tr[q].val <= v)
l = q,split(rs(q),v,rs(q),r);
else
r = q,split(ls(q),v,l,ls(q));
pushup(q);
}
inline int merge(int l,int r){
if (!l || !r) return l + r ;
if (tr[l].key < tr[r].key){
rs(l) = merge(rs(l),r);
pushup(l);
return l ;
}
ls(r) = merge(l,ls(r));
pushup(r);
return r ;
}
inline void insert(int &root,int v){
int x = 0,y = 0;
split(root,v,x,y);
root = merge(merge(x,mknode(v)),y);
}
inline void build(int q,int l,int r){
rep(i,l,r + 1) insert(root[q],a[i]);
if (l ^ r){
int mid = l + r >> 1;
build(q << 1,l,mid);
build(q << 1 | 1,mid + 1,r);
}
}
inline void del(int &root,int v){
int x,y,z;
split(root,v,x,y);
split(x,v-1,z,x);
x = merge(ls(x),rs(x));
root = merge(merge(z,x),y);
}
inline int getrk(int &root,int v){
int x,y,res;
split(root,v - 1,x,y);
res = tr[x].sz + 1;
root = merge(x,y);
return res ;
}
inline int get_rk(int q,int l,int r,int L,int R,int v){
if (L <= l && r <= R) return getrk(root[q],v) - 1;
int mid = l + r >> 1;
if (L > mid) return get_rk(q << 1 | 1,mid + 1,r,L,R,v);
if (R <= mid) return get_rk(q << 1,l,mid,L,R,v);
return get_rk(q << 1,l,mid,L,mid,v) + get_rk(q << 1 | 1,mid + 1,r,mid + 1,R,v);
}
inline int getk(int q,int k){
while (q){
if (tr[ls(q)].sz >= k) q = tr[q].ls ;
else if (tr[ls(q)].sz + 1 < k) k -= tr[ls(q)].sz + 1,q = tr[q].rs ;
else break ;
}
return tr[q].val;
}
inline int get_k(int q,int l,int r,int k){
int L = 0,R = 1e8,mid,res ;
while (L <= R){
mid = L + R >> 1;
if (get_rk(1,1,n,l,r,mid) + 1 <= k) L = mid + 1,res = mid ;
else R = mid - 1;
}
return res ;
}
inline void modify(int q,int l,int r,int pos,int v){
del(root[q],a[pos]);
insert(root[q],v);
if (l ^ r){
int mid = l + r >> 1;
if (pos > mid) modify(q << 1 | 1,mid + 1,r,pos,v);
else modify(q << 1,l,mid,pos,v);
}
}
inline int getpre(int &root,int v){
int x,y,res;
split(root,v - 1,x,y);
res = tr[x].sz ? getk(x,tr[x].sz) : -inf;
root = merge(x,y);
return res ;
}
inline int get_pre(int q,int l,int r,int L,int R,int v){
if (L <= l && r <= R) return getpre(root[q],v);
int mid = l + r >> 1;
if (L > mid) return get_pre(q << 1 | 1,mid + 1,r,L,R,v);
if (R <= mid) return get_pre(q << 1,l,mid,L,R,v);
return max(get_pre(q << 1,l,mid,L,mid,v),get_pre(q << 1 | 1,mid + 1,r,mid + 1,R,v));
}
inline int getsuf(int &root,int v){
int x,y,res;
split(root,v,x,y);
res = tr[y].sz ? getk(y,1) : inf;
root = merge(x,y);
return res ;
}
inline int get_suf(int q,int l,int r,int L,int R,int v){
if (L <= l && r <= R) return getsuf(root[q],v);
int mid = l + r >> 1;
if (L > mid) return get_suf(q << 1 | 1,mid + 1,r,L,R,v);
if (R <= mid) return get_suf(q << 1,l,mid,L,R,v);
return min(get_suf(q << 1,l,mid,L,mid,v),get_suf(q << 1 | 1,mid + 1,r,mid + 1,R,v));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int m,type,l,r,k;
cin >> n >> m ;
rep(i,1,n + 1) cin >> a[i];
build(1,1,n);
while (m --){
cin >> type ;
if (type == 3)
cin >> l >> k,modify(1,1,n,l,k),a[l] = k;
else {
cin >> l >> r >> k ;
if (type == 1)
cout << get_rk(1,1,n,l,r,k) + 1 << '\n';
else if (type == 2)
cout << get_k(1,l,r,k) << '\n';
else if (type == 4)
cout << get_pre(1,1,n,l,r,k) << '\n';
else if (type == 5)
cout << get_suf(1,1,n,l,r,k) << '\n';
}
}
return 0;
}