[bzoj 2827] 千山鸟飞绝

题意：二维平面上有n只鸟，每只鸟有威武值。t个命令依次执行，每个命令一瞬间将编号为v的鸟移动到(x,y)。定义一只鸟某时刻的士气值为和它在同一位置的其他鸟中威武值的最大值，某时刻的团结值为和它在同一位置的其他鸟的数目，求t个命令结束后每只鸟士气值最大值与团结值最大值的乘积。（1≤n≤30000，0≤t≤300000；坐标范围为整数，且不超过INT_MIN~INT_MAX；威武值为不超过INT_MAX的非负整数） 在最大士气值和最大团结值即时更新的假设下，一只鸟k的移动只影响到它自己和目标位置的鸟。对于目标位置的鸟，它们的最大士气值和k的威武值取max，最大团结值和目标位置的鸟数取max；对于k，它的最大士气值和目标位置鸟的威武值的最大值取max，最大团结值和目标位置的鸟数取max。

于是，离散化后动态维护每个位置鸟的集合即可，需要支持的操作有： - 插入 - 删除 - 求最大值 - 取max

手写一棵平衡树就好了。

{% raw %}
#include <cstdio>
#include <algorithm>
#define fst first
#define sec second
const int MAX_N = 3e4, MAX_T = 3e5;
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;

template<typename T>
inline T tension(T& x, T v)
{
	return x = max(x, v);
}

struct Bird {
	int v, w[2], o; // 威武值，士气值和团结值，p对应的编号
	ii p;
} B[MAX_N+1];

struct Cmd {
	int k;
	ii p;
} C[MAX_T];

struct Node {
	Node* ch[2], * fa;
	int r, k, t[2]; // 随机数，编号，士气值和团结值的tag

	void down(int d[2])
	{
		if (r == -1)
			return;
		for (int i = 0; i < 2; ++i) {
			tension(t[i], d[i]);
			tension(B[k].w[i], d[i]);
		}
	}

	void down()
	{
		ch[0]->down(t);
		ch[1]->down(t);
		t[0] = t[1] = 0;
	}

	void setc(int d, Node* x)
	{
		ch[d] = x;
		x->fa = this;
	}

	int type()
	{
		return this == fa->ch[1];
	}
} nodes[MAX_N+1], *root[MAX_N+MAX_T], *null = nodes;
int sz[MAX_N+MAX_T];

// Treap
// 以威武值为关键字

inline Node* rotate(Node* x, int d) // 需要先 push down
{
	Node* y = x->ch[d];
	if (x->fa)
		x->fa->setc(x->type(), y);
	else
		y->fa = 0;
	x->setc(d, y->ch[d^1]);
	y->setc(d^1, x);
	return y;
}
/* 插入可以写成循环，代码长度增加，易读性减弱，运行时间减少
void insert(int k, int o)
{
	++sz[o];
	int v = B[k].v, d;
	Node* x = 0, * y = root[o];
	while (y != null) {
		x = y;
		x->down();
		d = v > B[x->k].v;
		y = x->ch[d];
	}
	y = nodes + k;
	if (!x)
		root[o] = y;
	else {
		x->setc(d, y);
		while (y->r > x->r) {
			rotate(x, y->type());
			x = y->fa;
			if (!x) {
				root[o] = y;
				break;
			}
		}
	}
}
*/

void insert(Node* &x, int k, int v)
{
	if (x == null)
		x = nodes + k;
	else {
		x->down();
		int d = v > B[x->k].v;
		insert(x->ch[d], k, v);
		x->ch[d]->fa = x;
		if (x->ch[d]->r > x->r)
			x = rotate(x, d);
	}
}

void insert(int k, int o)
{
	++sz[o];
	insert(root[o], k, B[k].v);
}

void remove(int k, int o)
{
	static Node* S[MAX_N];
	int top = 0;
	for (Node* x = nodes + k; x; x = x->fa)
		S[top++] = x;
	while (top--)
		S[top]->down();
	--sz[o];
	Node* x = nodes + k;
	while (x->ch[0] != null || x->ch[1] != null) {
		int d = x->ch[1]->r > x->ch[0]->r;
		x->ch[d]->down();
		x->fa ? 0 : root[o] = x->ch[d];
		rotate(x, d);
	}
	if (x->fa) {
		x->fa->setc(x->type(), null);
		x->fa = 0;
	} else
		root[o] = null;
}

inline int maximum(Node* x)
{
	while (x->ch[1] != null)
		x = x->ch[1];
	return B[x->k].v;
}

void dfs(Node* x)
{
	if (x != null) {
		x->down();
		dfs(x->ch[0]);
		dfs(x->ch[1]);
	}
}

int m;
ii pos[MAX_N+MAX_T];

inline int idx(ii p)
{
	return lower_bound(pos, pos+m, p) - pos;
}

void move(int k, int o)
{
	if (root[o] != null) {
		int t[] = {B[k].v, sz[o]};
		root[o]->down(t);
		tension(B[k].w[0], maximum(root[o]));
		tension(B[k].w[1], sz[o]);
	}
	insert(k, o);
}

inline void init()
{
	srand(65535);
	null->r = -1;
	fill_n(root, m, null);
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d %d %d", &B[i].v, &B[i].p.fst, &B[i].p.sec);
		pos[m++] = B[i].p;
	}
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; ++i) {
		scanf("%d %d %d", &C[i].k, &C[i].p.fst, &C[i].p.sec);
		pos[m++] = C[i].p;
	}
	sort(pos, pos+m);
	m = unique(pos, pos+m) - pos;

	init();

	for (int i = 1; i <= n; ++i) {
		B[i].o = idx(B[i].p);
		nodes[i] = (Node){{null, null}, 0, rand(), i, {0, 0}};
		move(i, B[i].o);
	}

	for (int i = 0; i < t; ++i) {
		int to = idx(C[i].p), k = C[i].k;
		remove(k, B[k].o);
		move(k, to);
		B[k].o = to;
	}
	for (int i = 0; i < m; ++i)
		dfs(root[i]);
	for (int i = 1; i <= n; ++i)
		printf("%lld\n", (ll)B[i].w[0] * B[i].w[1]);
	return 0;
}
{% endraw %}