自动搬运

查看原文

来自洛谷，原作者为

	whx2009 (不AFO不改签)一片秋天的枫叶落在了地上，一把黑色的雨伞在叶下缓缓打开

搬运于2025-08-24 21:57:36，当前版本为作者最后更新于2024-12-10 15:57:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题思路：

这道题不要看他是紫题，其实很好写。

我们先考虑一种可以支持删除与求最大值和节点数的算法，这里我用的平衡树。我们可以用 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;
}