1588: [HNOI2002]营业额统计
题目:传送门
题解:
复习splay所以来刷个水。。。
题目描述不是特别清楚:应该是找第i天以前一个最小的营业额和第i天做差的最小值作为第i天的最小波动值
那就直接找前驱后继啊(不过定义要改一下,是可以相同的)
代码:
1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 struct node
8 {
9 int d,n,c,f,son[2];
10 }tr[110000];int len,root;
11 void add(int d,int f)
12 {
13 len++;tr[len].d=d;tr[len].n=tr[len].c=1;
14 tr[len].son[0]=tr[len].son[1]=0;tr[len].f=f;
15 if(d<tr[f].d)tr[f].son[0]=len;
16 else tr[f].son[1]=len;
17 }
18 void update(int x)
19 {
20 int lc=tr[x].son[0],rc=tr[x].son[1];
21 tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
22 }
23 int findip(int d)
24 {
25 int x=root;
26 while(tr[x].d!=d)
27 {
28 if(d<tr[x].d)
29 {
30 if(tr[x].son[0]==0)break;
31 else x=tr[x].son[0];
32 }
33 else
34 {
35 if(tr[x].son[1]==0)break;
36 else x=tr[x].son[1];
37 }
38 }
39 return x;
40 }
41 void rotate(int x,int w)
42 {
43 int f=tr[x].f,ff=tr[f].f;
44 int r,R;
45 r=tr[x].son[w],R=f;
46 tr[R].son[1-w]=r;
47 if(r!=0)tr[r].f=R;
48
49 r=x,R=ff;
50 if(tr[R].son[0]==f)tr[R].son[0]=r;
51 else tr[R].son[1]=r;
52 tr[r].f=R;
53
54 r=f,R=x;
55 tr[R].son[w]=r;
56 tr[r].f=R;
57
58 update(f);update(x);
59 }
60 void splay(int x,int rt)
61 {
62 while(tr[x].f!=rt)
63 {
64 int f=tr[x].f,ff=tr[f].f;
65 if(ff==rt)
66 {
67 if(tr[f].son[0]==x)rotate(x,1);
68 else rotate(x,0);
69 }
70 else
71 {
72 if(tr[ff].son[0]==f && tr[f].son[0]==x)rotate(f,1),rotate(x,1);
73 else if(tr[ff].son[1]==f && tr[f].son[1]==x)rotate(f,0),rotate(x,0);
74 else if(tr[ff].son[0]==f && tr[f].son[1]==x)rotate(x,0),rotate(x,1);
75 else if(tr[ff].son[1]==f && tr[f].son[0]==x)rotate(x,1),rotate(x,0);
76 }
77 }
78 if(rt==0)root=x;
79 }
80 void ins(int d)
81 {
82 if(root==0)
83 {
84 add(d,0);root=len;
85 return ;
86 }
87 int x=findip(d);
88 if(tr[x].d==d)
89 {
90 tr[x].n++;
91 update(x);
92 splay(x,0);
93 }
94 else
95 {
96 add(d,x);
97 update(x);
98 splay(len,0);
99 }
100 }
101 int findqianqu(int d)
102 {
103 int x=findip(d);splay(x,0);
104 if(d<tr[x].d && tr[x].son[0]!=0)
105 {
106 x=tr[x].son[0];
107 while(tr[x].son[1]!=0)x=tr[x].son[1];
108 }
109 if(d<tr[x].d)x=0;
110 return x;
111 }
112 int findhouji(int d)
113 {
114 int x=findip(d);splay(x,0);
115 if(d>tr[x].d && tr[x].son[1]!=0)
116 {
117 x=tr[x].son[1];
118 while(tr[x].son[0]!=0)x=tr[x].son[0];
119 }
120 if(d>tr[x].d)x=0;
121 return x;
122 }
123 int main()
124 {
125 int n;scanf("%d",&n);root=0;
126 int ans=0;int d;
127 scanf("%d",&d);ans+=d;ins(d);
128 for(int i=2;i<=n;i++)
129 {
130 scanf("%d",&d);int ss=999999999;
131 int lc=findqianqu(d),rc=findhouji(d);
132 if(lc!=0)ss=abs(tr[lc].d-d);
133 if(rc!=0)ss=min(abs(tr[rc].d-d),ss);
134 ans+=ss;ins(d);
135 }
136 printf("%d\n",ans);
137 return 0;
138 }
转载于:https://www.cnblogs.com/CHerish_OI/p/8795201.html