BZOJ 2827 千山鸟飞绝 Treap

题目描述#

话说有一天doyouloveme和vfleaking到山里玩。谁知doyouloveme刚刚进山，所有的鸟儿竟被他的神犇气场给惊得全部飞走了。vfleaking顿时膜拜不已。
这时鸟王用鸟语说道：“!@#$%……?”安抚了一下众鸟的情绪。鸟王生性好斗，作出了一个决定——要排鸟布阵把刚才吓到它们的人类赶出山去。

每只鸟都有一个编号，都有一个威武值。每秒钟鸟王都会发一个命令，编号为v的鸟飞到(x,y)去（坐标系原点是山顶，坐标单位为鸟爪）。鸟飞得很快，一秒之内就飞到了，可以看作是瞬间移动。如果编号为v的鸟和编号为u的鸟某一时刻处在同一位置，它们就会互相鼓励，增加各自的士气值和团结值。一只鸟的士气值等于此刻与它处在同一位置的鸟中的威武值的最大值，团结值等于此刻与它处在同一位置的鸟的只数。如果每一时刻都没有鸟与它处在同一位置，则士气值和团结值都为0。要注意自己不能鼓励自己，计算士气值和团结值时不能算上自己。 t秒钟后，doyouloveme目测出了现在每只鸟的战斗力，于是感叹了一句：“不妙，我们得走了。”
正所谓团结的鸟儿一个顶俩，所以doyouloveme这样描述战斗力：一只鸟战斗力值等于它在0到t秒中士气值的最大值与团结值的最大值的乘积。注意不是乘积的最大值，而是最大值的乘积。
vfleaking很想知道现在每只鸟的战斗力，但是他当然不会啦，于是他把这个任务交给了你来完成。

输入#

第一行一个数n，代表鸟的只数。（鸟王那家伙你可以完全忽视掉）
接下来n行，每行三个整数w,x,y描述每只鸟的威武值和初始坐标。第i+1行描述编号为i的鸟。
接下来一行有一个数t，代表经过时间ts。
接下来t行，每行三个整数v,x,y描述鸟王每秒的命令。

输出#

一共n行，每行一个数，代表每只鸟的战斗力。

样例输入#

样例输出#

提示#

对于样例的解释：首先5只鸟的位置为(1,1),(1,2),(4,4),(0,1),(2,3)，士气和团结值都是0。
鸟1飞到了(1,2)，于是鸟1和鸟2互相鼓励，鸟1士气变为3，鸟2士气变为1。鸟1鸟2的团结值变为1。
然后鸟2飞到(4,4)，与鸟3互相鼓励，鸟2士气变为4，鸟3士气变为3。鸟2与鸟3的团结值变为1。
鸟2然后飞到了(4,3)，一个没有鸟的地方。于是士气和团结值都变为了0。
接下来鸟3和鸟5都飞到了鸟4的位置，于是三只鸟互相鼓励，鸟4、鸟5士气变为4，鸟3士气仍为3。鸟3、鸟4、鸟5的团结值都变为2。
于是大家的战斗力：
鸟1：3 * 1 = 3
鸟2：4 * 1 = 4
鸟3：3 * 2 = 6
鸟4：4 * 2 = 8
鸟5：4 * 2 = 8
1≤n≤30000 0≤t≤300000
坐标范围为整数，且不超过INT_MIN~INT_MAX
威武值为不超过INT_MAX的非负整数。

题解#

哈希加Treap

把每一个点Hash对应的一棵Treap上
在插入和删除的时候不断的打标记跟新
注意不要漏情况
在最后的时候要把所有的标记都推下去
然后就出来了
细节很多调了好久

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
int Max_Morale[30005], Max_Solidarity[30005];
6
struct Point
7
{
8
    int x, y;
9
    Point(int a = 0, int b = 0)
10
    {
11
        x = a, y = b;
12
    }
13
    bool operator==(const Point &a) const
14
    {
15
        return x == a.x && y == a.y;
16
    }
17
};
18
struct data
19
{
20
    int x, ID;
21
    data(int a = 0, int b = 0)
22
    {
23
        x = a, ID = b;
24
    }
25
    bool operator>(const data &a) const
26
    {
27
        return x == a.x ? ID > a.ID : x > a.x;
28
    }
29
    bool operator<=(const data &a) const
30
    {
31
        return !(*this > a);
32
    }
33
};
34
struct Treap
35
{
36
    struct Node
37
    {
38
        int s, key, Max_Num, Max_Size;
39
        data x;
40
        Node *ch[2];
41
        Node(data sa)
42
        {
43
            ch[0] = ch[1] = NULL;
44
            s = 1, x = sa, key = rand();
45
            Max_Num = Max_Size = 0;
46
        }
47
#define size(_) ((_) ? (_)->s : 0)
48
        void Pushup()
49
        {
50
            s = size(ch[0]) + size(ch[1]) + 1;
51
        }
52
        void Pushdown()
53
        {
54
            if (ch[0])
55
            {
56
                ch[0]->Max_Num = max(ch[0]->Max_Num, Max_Num);
57
                ch[0]->Max_Size = max(ch[0]->Max_Size, Max_Size);
58
                Max_Morale[ch[0]->x.ID] = max(Max_Morale[ch[0]->x.ID], ch[0]->Max_Num);
59
                Max_Solidarity[ch[0]->x.ID] = max(Max_Solidarity[ch[0]->x.ID], ch[0]->Max_Size);
60
            }
61
            if (ch[1])
62
            {
63
                ch[1]->Max_Num = max(ch[1]->Max_Num, Max_Num);
64
                ch[1]->Max_Size = max(ch[1]->Max_Size, Max_Size);
65
                Max_Morale[ch[1]->x.ID] = max(Max_Morale[ch[1]->x.ID], ch[1]->Max_Num);
66
                Max_Solidarity[ch[1]->x.ID] = max(Max_Solidarity[ch[1]->x.ID], ch[1]->Max_Size);
67
            }
68
            Max_Num = Max_Size = 0;
69
        }
70
    } * root;
71
    Treap()
72
    {
73
        root = NULL;
74
    }
75
    Node *Merge(Node *A, Node *B)
76
    {
77
        if (!A)
78
            return B;
79
        if (!B)
80
            return A;
81
        if (A->key < B->key)
82
        {
83
            A->Pushdown();
84
            A->ch[1] = Merge(A->ch[1], B);
85
            A->Pushup();
86
            return A;
87
        }
88
        else
89
        {
90
            B->Pushdown();
91
            B->ch[0] = Merge(A, B->ch[0]);
92
            B->Pushup();
93
            return B;
94
        }
95
    }
96
    typedef pair<Node *, Node *> DNode;
97
    DNode Split(Node *rt, int k)
98
    {
99
        if (!rt)
100
            return DNode(NULL, NULL);
101
        DNode o;
102
        rt->Pushdown();
103
        if (size(rt->ch[0]) >= k)
104
        {
105
            o = Split(rt->ch[0], k);
106
            rt->ch[0] = o.second;
107
            rt->Pushup();
108
            o.second = rt;
109
        }
110
        else
111
        {
112
            o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
113
            rt->ch[1] = o.first;
114
            rt->Pushup();
115
            o.first = rt;
116
        }
117
        return o;
118
    }
119
    Node *kth(int k)
120
    {
121
        DNode x = Split(root, k - 1);
122
        DNode y = Split(x.second, 1);
123
        Node *ans = y.first;
124
        root = Merge(Merge(x.first, ans), y.second);
125
        return ans;
126
    }
127
    int Rank(Node *rt, data x)
128
    {
129
        if (!rt)
130
            return 0;
131
        return x <= rt->x ? Rank(rt->ch[0], x) : Rank(rt->ch[1], x) + size(rt->ch[0]) + 1;
132
    }
133
    void Insert(data x)
134
    {
135
        int k = Rank(root, x);
136
        if (root)
137
        {
138
            root->Max_Size = max(root->Max_Size, size(root));
139
            root->Max_Num = max(root->Max_Num, x.x);
140
            Max_Morale[root->x.ID] = max(root->Max_Num, Max_Morale[root->x.ID]);
141
            Max_Solidarity[root->x.ID] = max(root->Max_Size, Max_Solidarity[root->x.ID]);
142
        }
143
        DNode y = Split(root, k);
144
        Node *n = new Node(x);
145
        root = Merge(Merge(y.first, n), y.second);
146
    }
147
    void remove(data x)
148
    {
149
        int k = Rank(root, x);
150
        DNode a = Split(root, k);
151
        DNode b = Split(a.second, 1);
152
        delete b.first;
153
        root = Merge(a.first, b.second);
154
    }
155
};
156
#define Hash_MOD 76543
157
#define Hash_MOD_x 9991
158
#define Hash_MOD_y 7307
159
int p = 0;
160
struct Hash_Table
161
{
162
    int first[76545];
163
    struct Link
164
    {
165
        Treap *rt;
166
        Point t;
167
        int next;
168
    } v[400000];
169
    Hash_Table()
170
    {
171
        memset(first, -1, sizeof(first));
172
    }
173
    void Push(int u, Point now, Treap *x)
174
    {
175
        v[p].rt = x;
176
        v[p].t = now;
177
        v[p].next = first[u];
178
        first[u] = p++;
179
    }
180
    Treap *&operator[](Point x)
181
    {
182
        int Hash = (((x.x % Hash_MOD_x) + Hash_MOD_x) % Hash_MOD_x) * (((x.y % Hash_MOD_y) + Hash_MOD_y) % Hash_MOD_y) % Hash_MOD;
183
        for (int i = first[Hash]; i != -1; i = v[i].next)
184
            if (v[i].t == x)
185
                return v[i].rt;
186
        Push(Hash, x, new Treap);
187
        return v[first[Hash]].rt;
188
    }
189
} Hash;
190
#define X(_) ((_) ? (_)->x : 0)
191

192
Point bird[30005];
193
int Num[30005];
194
int main()
195
{
196
    int n;
197
    scanf("%d", &n);
198
    int a, b, c;
199
    for (int i = 1; i <= n; i++)
200
    {
201
        scanf("%d%d%d", &a, &b, &c);
202
        Max_Morale[i] = max(Max_Morale[i], X(Hash[Point(b, c)]->kth(size(Hash[Point(b, c)]->root))).x);
203
        Max_Solidarity[i] = max(Max_Solidarity[i], size(Hash[Point(b, c)]->root));
204
        Hash[Point(b, c)]->Insert(data(a, i));
205
        bird[i] = Point(b, c);
206
        Num[i] = a;
207
    }
208
    int m;
209
    scanf("%d", &m);
210
    for (int i = 1; i <= m; i++)
211
    {
212
        scanf("%d%d%d", &a, &b, &c);
213
        Hash[bird[a]]->remove(data(Num[a], a));
214
        Max_Morale[a] = max(Max_Morale[a], X(Hash[Point(b, c)]->kth(size(Hash[Point(b, c)]->root))).x);
215
        Max_Solidarity[a] = max(Max_Solidarity[a], size(Hash[Point(b, c)]->root));
216
        Hash[Point(b, c)]->Insert(data(Num[a], a));
217
        bird[a] = Point(b, c);
218
    }
219
    for (int i = 1; i <= n; i++)
220
        Hash[bird[i]]->remove(data(Num[i],i));
221
    for (int i = 1; i <= n; i++)
222
        printf("%lld\n", (long long)Max_Morale[i] * Max_Solidarity[i]);
223
    // while(1);
224
}