首页 > > 程序设计 > C/C++ >

[HNOI2002]-洛谷2234-营业额统计-Treap

2018-06-17 21:22:43来源：未知阅读 ()

第一道习题博客！！

这一道题比较简单。

题目就是输入一个数列。

就是每插入一个，找到前面插入过的与之差最小的值，将他们的差值加入答案。

这里可以想到平衡树。

每一次输入，加进treap中，然后找它的前驱和后继，比较他们的差值大小，小的加入答案。

如果treap不懂的话，可以看我的前一篇博客：http://www.cnblogs.com/justin-cao/p/8270272.html

贴一波代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<ctime>
 6 using namespace std;
 7 int n,root,size;
 8 long long ans,sum;
 9 long long inf=1000005;
10 long long a[50010];
11 struct P{
12     int l,r,sz,re,key,rd;
13 }t[50010];
14 void update(int k)
15 {
16     t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].re;
17 }
18 void left(int &k)
19 {
20     int y=t[k].r;
21     t[k].r=t[y].l;
22     t[y].l=k;
23     t[y].sz=t[k].sz;
24     update(k);
25     k=y;
26 }
27 void right(int &k)
28 {
29     int y=t[k].l;
30     t[k].l=t[y].r;
31     t[y].r=k;
32     t[y].sz=t[k].sz;
33     update(k);
34     k=y;
35 }
36 void init(int &k,int x)
37 {
38     if(k==0)
39     {
40         size++;
41         k=size;
42         t[k].sz=1;
43         t[k].re=1;
44         t[k].key=x;
45         t[k].rd=rand();
46         return;
47     }
48     t[k].sz++;
49     if(t[k].key==x)   t[k].re++;
50     else{
51         if(x>t[k].key)
52         {
53             init(t[k].r,x);
54             if(t[t[k].r].rd<t[k].rd)    left(k);
55         }
56         else{
57             init(t[k].l,x);
58             if(t[t[k].l].rd<t[k].rd)    right(k);
59         }
60     }
61 }
62 void pre(int k,int x)
63 {
64     if(k==0)  return;
65     if(t[k].key<=x)
66     {
67          ans=k;
68          pre(t[k].r,x);
69     }
70     else pre(t[k].l,x);
71 }
72 void nxt(int k,int x)
73 {
74     if(k==0)  return;
75     if(t[k].key>=x)
76     {
77         ans=k;
78         nxt(t[k].l,x);
79     }
80     else nxt(t[k].r,x);
81 }
82 int main()
83 {
84     srand(0);
85     scanf("%d",&n);
86     t[0].key=inf;
87     for(int i=1;i<=n;i++)  scanf("%lld",&a[i]);
88     init(root,a[1]);
89     for(int i=2;i<=n;i++)
90     {
91         pre(root,a[i]);
92         int x=ans;
93         nxt(root,a[i]);
94         sum+=(long long)min(abs(a[i]-t[x].key),abs(t[ans].key-a[i]));
95         init(root,a[i]);
96     }
97     printf("%lld",sum+a[1]);
98     return 0;
99 }