Luogu P2617 Dynamic Rankings 题解

(Updated: )
oi
, ,

Description

题目链接

给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$​，需要支持两种操作：

  • Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数
  • C x y 表示将 $a_x$​ 改为 $y$

Solution

树状数组套主席树

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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);
}
}
}