Steven_MengのBlog

传送门
平衡树模板题
也是模拟题
宠物和人会相互抵消,所以不存在一次操作后集合中既存在人也存在宠物
分情况讨论当前是人集合还是宠物集合
如果加进来的是同类,直接$Insert$
如果是不同类,查询前驱后继,按题目意思模拟即可

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 500005
#define MOD 1000000
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
namespace FHQ_Treap{
struct node{
int l,r;
int val;//每个点的权值
int pri;//优先级(随机生成)
int sz;
}tree[MAXN];
int tot;
#define lc(i) tree[i].l
#define rc(i) tree[i].r
inline void Update(int x){
tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;
}
inline int New(int v){
tree[++tot].val=v;
tree[tot].pri=rand();
tree[tot].sz=1;
return tot;
}
int Merge(int x,int y){
// printf("%d %d\n",x,y);
if (!x||!y) return x+y;
if (tree[x].pri<tree[y].pri){
rc(x)=Merge(rc(x),y),Update(x);
return x;
}
else {
lc(y)=Merge(x,lc(y)),Update(y);
return y;
}
}
void Split(int i,int k,int &x,int &y){
if (!i){//叶节点
x=y=0;
}
else {
if (tree[i].val<=k){x=i,Split(rc(i),k,rc(i),y);}
else{y=i,Split(lc(i),k,x,lc(i));}
Update(i);
}
}
int kth(int i,int k){//排名为k
while (true){
if (k<=tree[lc(i)].sz){
i=lc(i);
}
else if (k==tree[lc(i)].sz+1){
return i;
}
else{
k-=tree[lc(i)].sz+1;
i=rc(i);
}
}
}
//以上为FHQ Treap
int root,x,y,z;
void Init(){
tot=0;
memset(tree,0,sizeof(tree));
root=0;
srand(19260817);
}
inline void Add(int num){
Split(root,num,x,y);
root=Merge(Merge(x,New(num)),y);
}
inline void Del(int num){
Split(root,num,x,z);
Split(x,num-1,x,y);
y=Merge(lc(y),rc(y));
root=Merge(Merge(x,y),z);
}
inline int Rank(int num){//获得num排名
Split(root,num-1,x,y);
int temp=tree[x].sz+1;
root=Merge(x,y);
return temp;
}
#define Get_K(rt,rk) tree[kth(rt,rk)].val
inline int Kth(int k){//获得数组中第k大
return Get_K(root,k);
}
inline int Pre(int num){
Split(root,num-1,x,y);
int temp=Get_K(x,tree[x].sz);
root=Merge(x,y);
return temp;
}
inline int Nex(int num){
Split(root,num,x,y);
int temp=Get_K(y,1);
root=Merge(x,y);
return temp;
}
};
using namespace FHQ_Treap;
#define INF 0x3f3f3f3f
inline int Abs(int x){
return x>0?x:-x;
}
int main(){
Init();
int n=read();
Add(INF),Add(-INF);
int pets=0;//宠物数量
int man=0;//领养者数量
int ans=0;
for (register int i=1;i<=n;++i){
int opr=read(),p=read();
if (pets==man){//空树
Add(p);
}
else{
if ((opr==0&&pets>man)||(opr==1&&pets<man)){
Add(p);
}
else {
int pre=Pre(p),nex=Nex(p);
int d1=p-pre,d2=nex-p;
if (d1<=d2) ans+=d1,Del(pre);
else ans+=d2,Del(nex);
}
}
if (opr==0) pets++;
else man++;
ans%=MOD;
}
printf("%d\n",ans);
}

 评论