Steven_MengのBlog

传送门
平衡树模板题
模拟整个过程,每次找$num$的前驱后继,注意特判$num$在集合中的情况

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
// 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
int main(){
Init();
Add(INF),Add(-INF);
int ans=0;
int n=read();
int x=read();Add(x);
ans+=x;
for (register int i=2;i<=n;++i){
x=read();
if (Kth(Rank(x))!=x){
int pre=Pre(x),nex=Nex(x);
ans+=min(x-pre,nex-x);
}
Add(x);
}
printf("%d\n",ans);
}

 评论