题解：P4200 千山鸟飞绝
本题思路：
这道题不要看他是紫题，其实很好写。
我们先考虑一种可以支持删除与求最大值和节点数的算法，这里我用的平衡树。我们可以用 map 把坐标离散化，然后针对每一个坐标开一棵平衡树。把每一只鸟作为一个节点，以鸟的标号（输入顺序）建平衡树。这样的好处是可以直接在鸟的节点上记录最大的士气值与团结值。
然后我们知道求的是士气值的最大值与团结值的最大值的乘积，因为二者之间没有联系，我们就可以分开来看。
先看士气值，我们知道士气值是当前位置除了自己以外的最大威武值，这个还是很好维护的，移动时先分裂出当前节点，合并到他去的位置的平衡树上。合并的时候分别把两棵平衡树（可能有节点，我们在这里把节点看成一棵树）的最大值分别打在另一棵的懒标记上，分裂合并时下传更新最大士气值即可。
再来看团结值，这个更简单，直接在合并后再写一个懒标传下去即可（注意减一）。
初始赋值：
这里提一下，假设每一只鸟都先在一个互不重复的坐标集上，按照移动到初始位置的方式就和上面一样了。
本题代码：
#include<bits/stdc++.h>
#define int long long
#define ls tr[p].ch[0]
#define rs tr[p].ch[1]
using namespace std;
map<pair<int,int>,int>mp;
int a[30005];
struct f{int ch[2],siz,ma,id,ans1,ans2,add1,add2,rnd;}tr[30005];
void wei1(int p,int k){tr[p].ans1=max(tr[p].ans1,k),tr[p].add1=max(tr[p].add1,k);}
void wei2(int p,int k){tr[p].ans2=max(tr[p].ans2,k),tr[p].add2=max(tr[p].add2,k);}
void wei(int p){
tr[p].siz=tr[ls].siz+tr[rs].siz+1;
tr[p].ma=max(a[tr[p].id],tr[ls].ma);
tr[p].ma=max(tr[rs].ma,tr[p].ma);
}
void chuan(int p){
if(tr[p].add1){wei1(ls,tr[p].add1),wei1(rs,tr[p].add1);tr[p].add1=0;}
if(tr[p].add2){wei2(ls,tr[p].add2),wei2(rs,tr[p].add2);tr[p].add2=0;}
}
void split(int p,int &x,int &y,int k){
if(!p){x=y=0;return;}
if(tr[p].add1||tr[p].add2) chuan(p);
if(tr[p].id<=k){x=p;split(rs,rs,y,k);wei(x);}
else y=p,split(ls,x,ls,k),wei(y);
}
void merge(int &p,int x,int y){
if(!x||!y){p=x+y;return;}
if(tr[x].add1||tr[x].add2) chuan(x);
if(tr[y].add1||tr[y].add2) chuan(y);
if(tr[x].rnd<=tr[y].rnd) p=x,merge(rs,rs,y);
else p=y,merge(ls,x,ls);
wei(p);
}
int root[330005],cnt;
int add(int id){
tr[++cnt].id=id;tr[cnt].ma=a[id],tr[cnt].siz=1;
tr[cnt].rnd=rand();return cnt;
}
void merge1(int &x,int y){
wei1(y,tr[x].ma),wei1(x,tr[y].ma);
int xx,yy;
split(x,xx,yy,tr[y].id);
merge(xx,xx,y);
merge(x,xx,yy);
wei2(x,tr[x].siz-1);
}
int top=0;
int u[30005],v[30005];
signed main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
int x,y;cin>>x>>y;u[i]=x,v[i]=y;
if(mp[make_pair(x,y)]==0)mp[make_pair(x,y)]=++top;
int id=mp[make_pair(x,y)];
merge1(root[id],add(i));
}
int m;cin>>m;
for(int i=1;i<=m;i++){
int id,xx,yy;cin>>id>>xx>>yy;
int nowid=mp[make_pair(u[id],v[id])];
int x,y,z;
if(mp[make_pair(xx,yy)]==0) mp[make_pair(xx,yy)]=++top;
split(root[nowid],x,y,id);split(x,x,z,id-1);merge(root[nowid],x,y);
merge1(root[mp[make_pair(xx,yy)]],z);u[id]=xx,v[id]=yy;
}
for(int i=1;i<=n;i++){
int nowid=mp[make_pair(u[i],v[i])];
int x,y,z;
split(root[nowid],x,y,i);split(x,x,z,i-1);
merge(root[nowid],x,y);
cout<<tr[z].ans1*tr[z].ans2<<'\n';
}
return 0;
}