欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-21 20:34:08
第一道习题博客!! 这一道题比较简单。 题目就是输入一个数列。 就是每插入一个,找到前面插入过的与之差最小的值,将他们的差值加入答案。 这里可以想到平衡树。 每一次输入,加进treap中,然后找它的前驱和后继,比较他们的差值大小,小的加入答案。 如果treap不懂的话,可以看我的前一篇博客:http ......

第一道习题博客!!

这一道题比较简单。

题目就是输入一个数列。

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

这里可以想到平衡树。

每一次输入,加进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 }

题目链接:https://www.luogu.org/problemnew/show/2234或https://vjudge.net/problem/HYSBZ-1588

谢谢观看。

如有不对指出,请尽管提出,感激不尽!