P4422 题解

发表于
自己想出来的新做法！

题目

提供一种奇妙的平衡树做法。

以年龄为值建Treap。

由询问中年龄大于等于 $B$ 且最年轻的人，想到其实是查询 $B$ 的后继。

但注意到我们还需要保证这个人在第 $Y$ 站之前下车。

题目中有这样一句话：给出 $X$ 的顺序是随机的。

那我们为何不将下车的车站作为Treap中堆的优先级呢？

这样我们查询时就可以保证同时满足两个条件了。

放代码：

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define int long long
using namespace std;
int son[200005][2],fa[200005],sz[200005],num[200005],val[200005],pri[200005],cnt,inf=0x3f3f3f3f,root;
void update(int x){
	sz[x]=num[x];
	if(son[x][0])sz[x]+=sz[son[x][0]];
	if(son[x][1])sz[x]+=sz[son[x][1]];
}
void zig(int x){
	int s=son[x][0],ss=son[fa[x]][1]==x;
	if(x==root)root=s;
	son[x][0]=son[s][1];
	fa[son[s][1]]=x;
	son[s][1]=x;
	fa[s]=fa[x];
	son[fa[x]][ss]=s;
	fa[x]=s;
	update(x);
	update(s);
}
void zag(int x){
	int s=son[x][1],ss=son[fa[x]][1]==x;
	if(x==root)root=s;
	son[x][1]=son[s][0];
	fa[son[s][0]]=x;
	son[s][0]=x;
	fa[s]=fa[x];
	son[fa[x]][ss]=s;
	fa[x]=s;
	update(x);
	update(s);
}
void insert(int &x,int key,int loc,int f){
	if(!x){
		x=++cnt;
		val[x]=key;
		pri[x]=loc;
		num[x]=sz[x]=1;
		fa[x]=f;
		if(!f)root=x;
		return;
	}
	else sz[x]++;
	if(val[x]==key)num[x]++;
	else if(val[x]>key){
		insert(son[x][0],key,loc,x);
		if(pri[son[x][0]]<pri[x])zig(x);
	}
	else{
		insert(son[x][1],key,loc,x);
		if(pri[son[x][1]]<pri[x])zag(x);
	}
}
int query(int x,int key,int loc){
	if(pri[x]>loc)return inf;
	int ret=inf;
	if(val[x]>=key)ret=val[x];
	if(son[x][0]&&val[x]>=key)ret=min(ret,query(son[x][0],key,loc));
	if(son[x][1]&&val[x]<key)ret=min(ret,query(son[x][1],key,loc));
	return ret;
}
int read(){
	int num=0,fh=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')fh=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		num=(num<<3)+(num<<1)+c-'0';
		c=getchar();
	}
	return num*fh;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
signed main(){
	int n,q;
	cin>>n>>q;
	while(q--){
		char op;
		int a,b;
		do op=getchar();while(op!='M'&&op!='D');
		a=read(),b=read();
		if(op=='M'){
			insert(root,b,a,0);
		}
		else {
			int ans=query(root,b,a);
			if(ans==inf)printf("-1\n");
			else write(ans),putchar('\n');
		}
	}
	return 0;
}