洛谷 P1801 – 黑匣子 NOI 导刊 2010 提高 (06)

题面

思路

平衡树裸题,直接上板子。每次添加的时候 add ,查询的时候输出第 I 小的并更新 I 即可。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,y,l,r,size,cnt;
};
node s[1000001];
long long n,q,top=0;
long long root=0;
void update(long long x){
	s[x].size=s[s[x].l].size+s[s[x].r].size+s[x].cnt;
}
void rotr(long long &x){
	long long l=s[x].l;
	s[x].l=s[l].r;
	s[l].r=x;
	s[l].size=s[x].size;
	update(x);
	x=l;
}
void rotl(long long &x){
	long long r=s[x].r;
	s[x].r=s[r].l;
	s[r].l=x;
	s[r].size=s[x].size;
	update(x);
	x=r;
}
void add(long long &x,long long data){
	if (!x){
		x=++top;
		s[x].x=data;
		s[x].y=rand()%19260817;
		s[x].cnt=1;
		s[x].size=1;
		s[x].l=0;
		s[x].r=0;
		return;
	}
	s[x].size++;
	if (s[x].x==data){
		s[x].cnt++;
	}else if (data<s[x].x){
		add(s[x].l,data);
		if (s[x].y>s[s[x].l].y){
			rotr(x);
		}
	}else{
		add(s[x].r,data);
		if (s[x].y>s[s[x].r].y){
			rotl(x);
		}
	}
}
void del(long long &x,long long data){
	if (s[x].x==data){
		if (s[x].cnt>1){
			s[x].cnt--;
			s[x].size--;
			return;
		}
		if (!s[x].l||!s[x].r){
			x=s[x].l+s[x].r;
			return;
		}
		if (s[s[x].l].y<s[s[x].r].y){
			rotr(x);
			del(x,data);
		}else{
			rotl(x);
			del(x,data);
		}
		return;
	}
	s[x].size--;
	if (data<s[x].x){
		del(s[x].l,data);
	}else{
		del(s[x].r,data);
	}
}
long long pre(long long data){
	long long now=root,res=-2147483647;
	while (now){
		if (s[now].x<data){
			res=s[now].x;
			now=s[now].r;
		}else{
			now=s[now].l;
		}
	}
	return res;
}
long long nxt(long long data){
	long long now=root,res=2147483647;
	while (now){
		if (s[now].x>data){
			res=s[now].x;
			now=s[now].l;
		}else{
			now=s[now].r;
		}
	}
	return res;
}
long long querykth(long long k){
	long long now=root;
	while (now){
		if (s[s[now].l].size<k&&s[s[now].l].size+s[now].cnt>=k){
			return s[now].x;
		}
		if (s[s[now].l].size>=k){
			now=s[now].l;
		}else{
			k-=s[s[now].l].size+s[now].cnt;
			now=s[now].r;
		}
	}
	return 0;
}
long long queryrank(long long data){
	long long now=root,res=0;
	while (now){
		if (data==s[now].x){
			return res+s[s[now].l].size+1;
		}
		if (data<s[now].x){
			now=s[now].l;
		}else{
			res+=s[s[now].l].size+s[now].cnt;
			now=s[now].r;
		}
	}
	return res;
}
int a[1000000],b[1000000],I=0;
int m;
int main(){
	srand(time(0));
	cin>>q>>m;
	long long t,x;
	for (int i=1;i<=q;i++){
		cin>>a[i];
	}
	for (int i=1;i<=m;i++){
		cin>>b[i];
	}
	for (int i=1;i<=q;i++){
		add(root,a[i]);
		while (i==b[I+1]){
			I++;
			cout<<querykth(I)<<endl;
		}
	}
}
暂无评论

发送评论 编辑评论


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