题目链接：P4200 千山鸟飞绝

前置知识：FHQ Treap。

一、思路简述

你刚学习了平衡树，你想要练习，所以我们使用平衡树。

假设有 $q$ 个不同的坐标，所以我们建 $q$ 个平衡树，每个平衡树维护第 $id$ 个坐标的鸟，士气值维护一个最大值。

但是注意到题目中：

一只鸟战斗力值等于它在 $0$ 到 $t$ 秒中士气值的最大值与团结值的最大值的乘积。注意不是乘积的最大值，而是最大值的乘积。

所以我们的最大值是动态变化的，但是战斗力值不是，所以还要维护历史最大值。

但是如果加入了一个最大值，我们整个平衡树都要变成这个值，但是每次都更新整棵树太浪费时间了，所以我们借鉴线段树的懒标记。

还有一个值是团结值，是维护整个平衡树的大小减去一，因为不包括自己，但是也是每次更新太麻烦了，所以再来一个懒标记。

然后就是合并与分裂，没什么好说的。

二、代码展示

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+100;
int n,m,root[N],u[N],v[N],tot,cnt,a[N];
struct node{
	int l,r,sz,ma,id,ans,ans2,tag,tag2,rn;
}e[N];
map<pair<int,int>,int> s;
int create(int k,int x){
	e[++tot]={0,0,1,k,x,0,0,0,0,rand()};return tot;
}
void push_up(int p){
	e[p].sz=e[e[p].l].sz+e[e[p].r].sz+1;
	e[p].ma=max(a[e[p].id],e[e[p].l].ma);
	e[p].ma=max(e[p].ma,e[e[p].r].ma);
}
void push_down(int p){
	if(e[p].tag){
		e[e[p].l].ans=max(e[p].tag,e[e[p].l].ans);
		e[e[p].l].tag=max(e[p].tag,e[e[p].l].tag);
		e[e[p].r].ans=max(e[p].tag,e[e[p].r].ans);
		e[e[p].r].tag=max(e[p].tag,e[e[p].r].tag);
		e[p].tag=0;
	}
	if(e[p].tag2){
		e[e[p].l].ans2=max(e[p].tag2,e[e[p].l].ans2);
		e[e[p].l].tag2=max(e[p].tag2,e[e[p].l].tag2);
		e[e[p].r].ans2=max(e[p].tag2,e[e[p].r].ans2);
		e[e[p].r].tag2=max(e[p].tag2,e[e[p].r].tag2);
		e[p].tag2=0;
	}
}
void split(int p,int k,int &x,int &y){
	if(!p){x=0,y=0;return;}
	push_down(p);
	if(e[p].id<=k){
		x=p;split(e[x].r,k,e[x].r,y);push_up(p);
	}
	else{
		y=p;split(e[y].l,k,x,e[y].l);push_up(p);
	}
}
int merge(int x,int y){
	if(x==0||y==0)return x+y;
	push_down(x);push_down(y);
	if(e[x].rn<=e[y].rn){
		e[x].r=merge(e[x].r,y);push_up(x);return x;
	}
	else{
		e[y].l=merge(x,e[y].l);push_up(y);return y;
	}
}
int insert(int x,int y){
	e[y].ans=max(e[x].ma,e[y].ans); e[y].tag=max(e[y].tag,e[x].ma);
	e[x].ans=max(e[x].ans,a[e[y].id]); e[x].tag=max(e[x].tag,a[e[y].id]);
	int c,d; split(x,e[y].id,c,d); x=merge(merge(c,y),d);
	e[x].ans2=max(e[x].ans2,e[x].sz-1); e[x].tag2=max(e[x].tag2,e[x].sz-1);
	return x;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		pair<int,int> p;cin>>a[i]>>u[i]>>v[i];
		if(s[{u[i],v[i]}]==0)s[{u[i],v[i]}]=++cnt;
		int id=s[{u[i],v[i]}];
		root[id]=insert(root[id],create(a[i],i));
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int id,x,y,z;pair<int,int> p;cin>>id>>p.first>>p.second;
		int zusu=s[{u[id],v[id]}];split(root[zusu],id,x,y);
		split(x,id-1,x,z);root[zusu]=merge(x,y);
		if(s[p]==0)s[p]=++cnt;root[s[p]]=insert(root[s[p]],z);
		u[id]=p.first;v[id]=p.second;
	}
	for(int i=1;i<=n;i++){
		int x,y,z,zusu=s[{u[i],v[i]}];
		split(root[zusu],i,x,y);split(x,i-1,x,z);
		cout<<e[z].ans*e[z].ans2<<'\n';root[zusu]=merge(x,y);
	}
	return 0;
}