害啊，改了一下，二十分了，其余wa的地方都是很靠后的数据wa掉了，球球救救孩子
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=5e4+5;
const double alpha=0.7;
int cnt,ldr[100001],rt,num[100001];
struct scape{
int ls,rs,w,wn,s,sz,sd;
}t[MAXN*30];
inline void calc(int k){
t[k].s=t[t[k].ls].s+t[t[k].rs].s+1;
t[k].sz=t[t[k].ls].sz+t[t[k].rs].sz+t[k].wn;
t[k].sd=t[t[k].ls].sd+t[t[k].rs].sd+(t[k].wn!=0);
}
inline int newnode(int w){
++cnt;
t[cnt].ls=t[cnt].rs=0;
t[cnt].w=w;t[cnt].wn=t[cnt].s=t[cnt].sz=t[cnt].sd=1;
return cnt;
}
inline bool check(int k){
return t[k].wn&&(alpha*t[k].s<=(double)max(t[t[k].ls].s,t[t[k].rs].s)||(double)t[k].sd<=alpha*t[k].s);
}
inline void pai(int& ldc,int k){
if(!k) return ;
pai(ldc,t[k].ls);
if(t[k].wn) ldr[ldc++]=k;
pai(ldc,t[k].rs);
}
inline int rebuild(int l,int r){
int mid=(l+r)/2;
if(l>=r) return 0;
t[ldr[mid]].ls=rebuild(l,mid);
t[ldr[mid]].rs=rebuild(mid+1,r);
calc(ldr[mid]);
return ldr[mid];
}
inline void re(int& k){
int ldc=0;
pai(ldc,k);
k=rebuild(0,ldc);
}
inline void ins(int& k,int p){
if(!k) k=newnode(p);
else{
if(p==t[k].w) t[k].wn++;
else if(p<t[k].w) ins(t[k].ls,p);
else ins(t[k].rs,p);
calc(k);
if(check(k)) re(k);
}
}
inline void del(int& k,int p){
if(!k) return ;
else{
if(t[k].w==p){
if(t[k].wn) t[k].wn--;
}else if(p<t[k].w) del(t[k].ls,p);
else del(t[k].rs,p);
calc(k);
if(check(k)) re(k);
}
}
inline int upb(int k,int p){
if(!k) return 1;
else if(t[k].w==p&&t[k].wn) return t[t[k].ls].sz+1+t[k].wn;
else if(t[k].w<p) return t[t[k].ls].sz+t[k].wn+upb(t[k].rs,p);
else return upb(t[k].ls,p);
}
inline int fpb(int k,int p){
if(!k) return 0;
else if(t[k].w==p&&t[k].wn) return t[t[k].ls].sz;
else if(t[k].w<p) return t[t[k].ls].sz+t[k].wn+fpb(t[k].rs,p);
else return fpb(t[k].ls,p);
}
inline int at(int k,int p){
if(!k) return -1;
else if(t[t[k].ls].sz<p&&t[t[k].ls].sz+t[k].wn>=p) return t[k].w;
else if(t[t[k].ls].sz+t[k].wn<p) return at(t[k].rs,p-t[t[k].ls].sz-t[k].wn);
else return at(t[k].ls,p);
}
inline int qianqu(int k,int p){
int t=at(k,fpb(k,p));
if(t==-1) t=-2147483647;
return t;
}
inline int houji(int k,int p){
int t=at(k,upb(k,p));
if(t==-1) t=2147483647;
return t;
}
struct segment{
int l,r,root;
}a[MAXN*10];
inline void build(int p,int l,int r){
a[p].l=l,a[p].r=r;
for(int i=l;i<=r;i++) ins(a[p].root,num[i]);
if(l==r) return ;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
inline void change(int p,int x,int y){
del(a[p].root,num[x]);
ins(a[p].root,y);
if(a[p].l==a[p].r) return ;
int mid=(a[p].l+a[p].r)/2;
if(x<=mid) change(p*2,x,y);
if(x>mid) change(p*2+1,x,y);
}
inline int queryrank(int p,int l,int r,int k){
if(a[p].l>r||a[p].r<l) return 0;
if(a[p].l>=l&&a[p].r<=r){
//cout<<a[p].l<<" "<<a[p].r<<" "<<fpb(a[p].root,k)+1<<endl;
return fpb(a[p].root,k);
}else return queryrank(p*2,l,r,k)+queryrank(p*2+1,l,r,k);
}
inline int querynum(int l,int r,int k){
int le=0,ri=1e8,ans;
while(le<=ri){
// cout<<le<<" "<<ri<<endl;
int mid=(le+ri)/2;
//cout<<mid<<" "<<queryrank(1,l,r,mid)+1<<" "<<k<<endl;
if(queryrank(1,l,r,mid)+1>k){
ri=mid-1;
}else le=mid+1,ans=mid;
}
return ans;
}
inline int querypre(int p,int l,int r,int k){
if(a[p].l>r||a[p].r<l) return -2147483647;
if(a[p].l>=l&&a[p].r<=r) return qianqu(a[p].root,k);
else return max(querypre(p*2,l,r,k),querypre(p*2+1,l,r,k));
}
inline int queryhou(int p,int l,int r,int k){
if(a[p].l>r||a[p].r<l) return 2147483647;
if(a[p].l>=l&&a[p].r<=r) return houji(a[p].root,k);
else return min(queryhou(p*2,l,r,k),queryhou(p*2+1,l,r,k));
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
build(1,1,n);
//cout<<queryrank(1,1,5,10)+1<<endl;
for(int i=0;i<m;i++){
int opt,l,r,k;
scanf("%d%d%d",&opt,&l,&r);
if(opt==1){
scanf("%d",&k);
printf("%d\n",queryrank(1,l,r,k)+1);
}else if(opt==2){
scanf("%d",&k);
printf("%d\n",querynum(l,r,k));
}else if(opt==3){
change(1,l,r);
}else if(opt==4){
scanf("%d",&k);
printf("%d\n",querypre(1,l,r,k));
}else{
scanf("%d",&k);
printf("%d\n",queryhou(1,l,r,k));
}
}
return 0;
}
```
by memory_frv @ 2021-08-26 16:00:17
巧了……我这个题就写的替罪羊
by SDNetFriend @ 2021-09-05 17:17:27
https://www.luogu.com.cn/paste/g8kouvo0
by SDNetFriend @ 2021-09-05 17:18:04
捕捉憨憨
by 在中路数星星ε @ 2021-11-05 16:09:21