「bzoj2827」千山鸟飞绝 - treap/带标记堆+历史最值 | Bill Yang's Blog

「bzoj2827」千山鸟飞绝 - treap/带标记堆+历史最值

题目大意

    话说有一天doyouloveme和vfleaking到山里玩。谁知doyouloveme刚刚进山,所有的鸟儿竟被他的神犇气场给惊得全部飞走了。vfleaking顿时膜拜不已。
    这时鸟王用鸟语说道:“!@#%……?”安抚了一下众鸟的情绪。鸟王生性好斗,作出了一个决定——要排鸟布阵把刚才吓到它们的人类赶出山去。
    每只鸟都有一个编号,都有一个威武值。每秒钟鸟王都会发一个命令,编号为$v$的鸟飞到$(x,y)$去(坐标系原点是山顶,坐标单位为鸟爪)。鸟飞得很快,一秒之内就飞到了,可以看作是瞬间移动。如果编号为$v$的鸟和编号为$u$的鸟某一时刻处在同一位置,它们就会互相鼓励,增加各自的士气值和团结值。一只鸟的士气值等于此刻与它处在同一位置的鸟中的威武值的最大值,团结值等于此刻与它处在同一位置的鸟的只数。如果每一时刻都没有鸟与它处在同一位置,则士气值和团结值都为$0$。要注意自己不能鼓励自己,计算士气值和团结值时不能算上自己。
    $t$秒钟后,doyouloveme目测出了现在每只鸟的战斗力,于是感叹了一句:“不妙,我们得走了。”
    正所谓团结的鸟儿一个顶俩,所以doyouloveme这样描述战斗力:一只鸟战斗力值等于它在$0$到$t$秒中士气值的最大值与团结值的最大值的乘积。注意不是乘积的最大值,而是最大值的乘积。
    vfleaking很想知道现在每只鸟的战斗力,但是他当然不会啦,于是他把这个任务交给了你来完成。


题目分析

这道题即:有很多个鸟飞来飞去,要你统计每个鸟经过的位置集合中其他鸟的权值最大值与集合大小最大值。

坐标太大,给坐标离散化成不同集合。
不难想到使用treap直接维护。
用堆也可以,不过要手写标记下传。


代码

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int max(int a,int b) {
return a>b?a:b;
}
const int maxn=330005;
int cnt,a[maxn],tmp[maxn],ans1[maxn],ans2[maxn];
struct Tree {
int child[2];
int d;
int size;
int lazy1,lazy2;
} tree[maxn];
struct Treap {
int root;
#define d(x) tree[x].d
#define val(x) a[x]
#define lazy1(x) tree[x].lazy1
#define lazy2(x) tree[x].lazy2
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define size(x) tree[x].size
void push_up(int index) {
int ls=ls(index),rs=rs(index);
size(index)=size(ls)+size(rs)+1;
}
void push_down(int index) {
if(!lazy1(index)&&!lazy2(index))return;
int ls=ls(index),rs=rs(index);
if(ls)update(ls,lazy1(index),lazy2(index));
if(rs)update(rs,lazy1(index),lazy2(index));
lazy1(index)=lazy2(index)=0;
}
void update(int now,int a,int b) {
ans1[now]=max(ans1[now],a);
ans2[now]=max(ans2[now],b);
lazy1(now)=max(lazy1(now),a);
lazy2(now)=max(lazy2(now),b);
}
void newnode(int now) {
d(now)=rand()*rand()%maxn;
size(now)=1;
ls(now)=rs(now)=lazy1(now)=lazy2(now)=0;
}
void rotate(int& index,bool side) {
int son=tree[index].child[side^1];
tree[index].child[side^1]=tree[son].child[side];
tree[son].child[side]=index;
push_up(index);
push_up(son);
index=son;
}
void insert(int& index,int now) {
if(!index) {
newnode(now);
index=now;
return;
}
push_down(index);
bool side=val(now)>val(index)||(val(now)==val(index)&&now>index);
int &son=tree[index].child[side];
insert(son,now);
size(index)++;
if(d(index)<d(son))rotate(index,side^1);
}
void dfs(int index) {
if(!index)return;
push_down(index);
if(ls(index))dfs(ls(index));
tmp[++cnt]=index;
if(rs(index))dfs(rs(index));
}
int build(int Left,int Right) {
if(Left>Right)return 0;
int mid=(Left+Right)>>1,now=tmp[mid];
newnode(now);
ls(now)=build(Left,mid-1);
rs(now)=build(mid+1,Right);
push_up(now);
return now;
}
int rebuild(int index) {
cnt=0;
dfs(ls(index));
dfs(rs(index));
int pos=build(1,cnt);
return pos;
}
void remove(int id) {
int now=root,father,val=val(id);
bool side;
while(val(now)!=val||now!=id) {
father=now;
push_down(now);
size(now)--;
if(val<val(now)||(val==val(now)&&id<now))now=ls(now),side=0;
else now=rs(now),side=1;
}
push_down(now);
int pos=rebuild(now);
if(now!=root)tree[father].child[side]=pos;
else root=pos;
}
int get_max(int now) {
push_down(now);
if(!rs(now))return val(now);
return get_max(rs(now));
}
} treap[maxn];
int n,t,pos[maxn],step=0;
map<int,map<int,int> >M;
int Hash(int x,int y) {
if(M.count(x)&&M[x].count(y))return M[x][y];
return M[x][y]=++step;
}
void Insert(int p,int id) {
if(treap[p].root) {
ans1[id]=max(ans1[id],treap[p].get_max(treap[p].root));
treap[p].update(treap[p].root,a[id],0);
}
treap[p].insert(treap[p].root,id);
treap[p].update(treap[p].root,0,tree[treap[p].root].size-1);
}
int main() {
srand(99995999);
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
int x=Get_Int(),y=Get_Int();
pos[i]=Hash(x,y);
Insert(pos[i],i);
}
t=Get_Int();
while(t--) {
int id=Get_Int(),x=Get_Int(),y=Get_Int(),p=Hash(x,y);
treap[pos[id]].remove(id);
pos[id]=p;
Insert(p,id);
}
for(int i=1; i<=n; i++)treap[pos[i]].remove(i); //传递标记
for(int i=1; i<=n; i++)printf("%lld\n",(long long)ans1[i]*ans2[i]);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%