bzoj 2827 千山鸟飞绝

bzoj 2827 千山鸟飞绝

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

Input

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

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

Sample Input 5 1 1 1 3 1 2 4 4 4 2 0 1 2 2 3 5 1 1 2 2 4 4 2 4 3 3 0 1 5 0 1 Sample Output 3 4 6 8 8 HINT 对于样例的解释： 首先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的非负整数。

Source 湖北省队互测

仔细读题发现很难写

每个坐标维护一个splay 然后splay上维护两个标记 tag1,tag2分别表示我当前这个节点收到的影响最大的值和e这个点和最多有多少点在一起

注意rt个数和操作次数有关..N*10

然后删除的时候因为我的写法导致如果是边界情况 那么会导致tag标记不能完全下放 所以在回答询问的时候需要取max来确定tag标记

#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。