Luogu P2617 Dynamic Rankings 题解
Description
题目链接
给定一个含有 n 个数的序列 a_1,a_2 dots a_n，需要支持两种操作：
- Q l r k 表示查询下标在区间 [l,r] 中的第 k 小的数
- C x y 表示将 a_x 改为 y
Solution
树状数组套主席树
Code
代码语言：javascript复制#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 '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("%dn",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);
}
}
} 
