Luogu P2617 Dynamic Rankings 题解

#include<bits/stdc++.h>
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch&15),ch=getchar();
return res*f; 
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+'0');
else write(x/10),putchar(x%10+'0');
}
int n,m,a[100010],Q[100010<<1],cnt,tot,rt[100010<<1];
vector<int> del,add;
struct Question{int op,l,r,x;}q[100010];
struct node{int l,r,sum,sz;}tr[60000010];
inline void insert(int &x,int l,int r,int pos,int v){
if(!x) ++tot,tr[tot]=tr[x],x=tot;
tr[x].sum+=v;
if(l==r) return ;
int mid=l+r>>1;
if(pos<=mid) insert(tr[x].l,l,mid,pos,v);
else insert(tr[x].r,mid+1,r,pos,v);
}
inline int query(int l,int r,int x){
if(l==r) return l;
int res=0,mid=l+r>>1;
for(auto i:del) res-=tr[tr[i].l].sum;
for(auto i:add) res+=tr[tr[i].l].sum;
if(x<=res){
for(auto &i:del) i=tr[i].l;
for(auto &i:add) i=tr[i].l;
return query(l,mid,x);
}else{
for(auto &i:del) i=tr[i].r;
for(auto &i:add) i=tr[i].r;
return query(mid+1,r,x-res);
}
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++) a[i]=read(),Q[++cnt]=a[i];
for(int i=1;i<=m;i++){
char c;cin>>c;
if(c=='Q') q[i].op=1,q[i].l=read(),q[i].r=read(),q[i].x=read();
else q[i].op=2,q[i].l=read(),q[i].x=read(),Q[++cnt]=q[i].x;
}
sort(Q+1,Q+cnt+1);
cnt=unique(Q+1,Q+cnt+1)-Q-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(Q+1,Q+cnt+1,a[i])-Q;
for(int i=1;i<=m;i++)
if(q[i].op==2) q[i].x=lower_bound(Q+1,Q+cnt+1,q[i].x)-Q;
for(int i=1;i<=n;i++)
for(int j=i;j<=cnt;j+=(j&(-j))) insert(rt[j],1,cnt,a[i],1);
for(int i=1;i<=m;i++){
if(q[i].op==1){
del.clear();add.clear();
for(int j=q[i].l-1;j;j-=(j&(-j))) del.push_back(rt[j]);
for(int j=q[i].r;j;j-=(j&(-j))) add.push_back(rt[j]);
printf("%d\n",Q[query(1,cnt,q[i].x)]);
}else{
for(int j=q[i].l;j<=cnt;j+=(j&(-j))) insert(rt[j],1,cnt,a[q[i].l],-1);
a[q[i].l]=q[i].x;
for(int j=q[i].l;j<=cnt;j+=(j&(-j))) insert(rt[j],1,cnt,a[q[i].l],1);
}
}
}