HNOI2002 营业额统计平衡树模板题【splay】

HNOI2002 营业额统计

题意见链接。。

题目大意：每读入一个数，在前面找一个与该数差最小的，统计答案。

一看就平衡树模板题，这里我用 Splay。

splay 简单介绍一下啊：

几个操作：

1、插入 NewNode ：维护堆一样的有序性：左小右大，重复的不插入。

2、插完以后 splay 把节点转到目标节点goal 下面。

3、旋转操作： rotate ：

　　又分三种情况：

　　1：pre[pre[x]]==goal 直接旋上去。

　　2：pre[pre[x]]!=goal 且 x 与 pre[x] 与 pre[pre[x]] 三点共线（即同侧），先把 pre[x]旋上去，再把 x 按相同的方向旋上去。

　　3: pre[pre[x]]!=goal 且 x、pre[x]、pre[pre[x]] 异侧，则先把pre[x]旋上去，再把 x 按相反的方向旋上去。

4、前趋、后继：

这个很简单吧，和二叉排序树一样，一直往下找就可以了。

本题代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+5,INF=0x3f3f3f3f;
 4 int n;
 5 int pre[N],key[N],ch[N][2],rt,tot1;
 6 inline void NewNode(int &r,int fa,int k)
 7 {
 8     r=++tot1; pre[r]=fa; key[r]=k;
 9     ch[r][0]=ch[r][1]=0;
10 }
11 inline void rotate(int x,int kd)
12 {
13     int y=pre[x];
14     ch[y][!kd]=ch[x][kd];
15     pre[ch[x][kd]]=y;
16     if (pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;
17     pre[x]=pre[y];
18     ch[x][kd]=y;
19     pre[y]=x;
20 }
21 inline void splay(int r,int goal)
22 {
23     while (pre[r]!=goal)
24     {
25         if (pre[pre[r]]==goal) rotate(r,ch[pre[r]][0]==r);
26         else 
27         {
28             int y=pre[r];
29             int kd=ch[pre[y]][0]==y;
30             if (ch[y][kd]==r)
31             {
32                 rotate(r,!kd); rotate(r,kd);
33             }
34             else {
35                 rotate(y,kd); rotate(r,kd);
36             }
37         }
38     }
39     if (goal==0) rt=r;
40 }
41 inline int Insert(int k)
42 {
43     int r=rt;
44     while (ch[r][key[r]<k])
45     {
46         if (key[r]==k)
47         {
48             splay(r,0);
49             return 0;
50         }
51         r=ch[r][key[r]<k];
52     }
53     NewNode(ch[r][key[r]<k],r,k);
54     splay(ch[r][key[r]<k],0);
55     return 1;
56 }
57 inline int getp(int x)
58 {
59     int tmp=ch[x][0];
60     if (tmp==0) return INF;
61     while (ch[tmp][1])
62       tmp=ch[tmp][1];
63     return key[x]-key[tmp];
64 }
65 inline int getn(int x)
66 {
67     int tmp=ch[x][1];
68     if (tmp==0) return INF;
69     while (ch[tmp][0])
70       tmp=ch[tmp][0];
71     return key[tmp]-key[x];
72 }
73 int main()
74 {
75     rt=tot1=0;
76     scanf("%d",&n);
77     int ans=0;
78     for (int i=1; i<=n; ++i)
79     {
80         int num;
81         if (scanf("%d",&num)==EOF) num=0;
82         if (i==1)
83         {
84             ans+=num;
85             NewNode(rt,0,num);
86             continue;
87         }
88         if (Insert(num)==0) continue;
89         int a=getp(rt),b=getn(rt);
90         ans+=min(a,b);
91     }
92     printf("%d
",ans);
93     return 0;
94 }

View Code

fighting fighting fighting!!!

HNOI2002 营业额统计 平衡树模板题 【splay】

HNOI2002 营业额统计

HNOI2002 营业额统计平衡树模板题【splay】