[HNOI 2002] 营业额统计

题意:

给出每天的营业额,求出与之前营业额的最小差值加入答案。

很明显的平衡树,只要注意特殊情况和判重即可。

关于平衡树,可以看这史上最详尽的平衡树(splay)讲解与模板

其中代码都是非指针的。


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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<climits>

using namespace std;

struct node
{
    int lefson, rigson, val, cnt, fat, tot;
    node()
    {
        lefson = -1;
        rigson = -1;
        val = INT_MAX;
        cnt = 1;
        fat = -1;
    }
}trees[2000010];

int tot = 1, Root = 1;

int Input(int x, int root)
{
    if (trees[root].val == x)
    {
        trees[root].cnt++;
        return root;
    }
    if (trees[root].val == INT_MAX)
    {
        trees[root].val = x;
        trees[root].tot = tot;
        return tot;
    }
    if (trees[root].val > x)
    {
        if (trees[root].lefson == -1)
        {
            trees[root].lefson = ++tot;
            trees[trees[root].lefson].fat = root;
        }
        return Input(x, trees[root].lefson);
    }
    if (trees[root].val < x)
        if (trees[root].rigson == -1)
        {
            trees[root].rigson = ++tot;
            trees[trees[root].rigson].fat = root;
        }
    return Input(x, trees[root].rigson);  
}

void Output(int root)
{
    if (trees[root].lefson != -1)
        Output(trees[root].lefson);
    for (int i = 1;i <= trees[root].cnt; i++)
        printf("%d ", trees[root].val);
    if (trees[root].rigson != -1)
        Output(trees[root].rigson);
}

int L_R(int x)
{
    if (trees[trees[x].fat].lefson == x) return 0;
    return 1;
}

void rotate(int x)
{
    int y = trees[x].fat, reat = L_R(x), fa = L_R(y);
    if (!reat)
    {
        trees[y].lefson = trees[x].rigson;
        trees[trees[y].lefson].fat = y;
        trees[x].rigson = y;
    }
    else
    {
        trees[y].rigson = trees[x].lefson;
        trees[trees[y].rigson].fat = y;
        trees[x].lefson = y;
    }
    trees[x].fat = trees[y].fat;
    trees[y].fat = x;
    if (trees[x].fat != -1)
    {
        if (!fa)
            trees[trees[x].fat].lefson = x;
        else
            trees[trees[x].fat].rigson = x;
    }
}

void splay(int x)
{
    int y = trees[x].fat;
    while (y != - 1)
    {
        if (trees[y].fat != - 1)
            rotate(L_R(x) + L_R(y) == 1?y:x);
        rotate(x);
        y = trees[x].fat;
    }
    Root = x;
}

int More(int root)
{
    if (trees[root].lefson != -1)
        return More(trees[root].lefson);
    return trees[root].val;
}

int Less(int root)
{
    if (trees[root].rigson != - 1)
        return Less(trees[root].rigson);
    return trees[root].val;
}

int main(void)
{
    freopen("avl.in","r",stdin);
    freopen("avl.out","w",stdout);
   
    int n, x;
    long long ans = 0;
    cin >> n;
    for (int i = 1;i <= n; i++)
    {
       scanf("%d", &x);
       splay(Input(x, Root));
       if (i == 1)
       {
           ans = x;
           continue;
       }
       if (trees[Root].cnt > 1) continue;
       ans += min(abs(x - (trees[Root].rigson != -1?More(trees[Root].rigson):INT_MAX)), abs(x - (trees[Root].lefson != -1?Less(trees[Root].lefson):INT_MAX)));
    }
    cout << ans;
   
    fclose(stdin);
    fclose(stdout);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注