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

#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);
		}
	}
} 
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇