自动搬运

查看原文

来自洛谷，原作者为

	pig1121 只要坐骑的志向在战场，被什么骑并不重要

搬运于2025-08-24 23:01:41，当前版本为作者最后更新于2024-12-23 13:48:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑线段树合并。

先试图用线段树表示状态。注意到合并是中心对齐且 $2\mid a_i$，故只需要维护正方形的一角（输出时将答案乘以 $4$）。某一个位置的颜色只与它到中心的水平（或竖直）距离有关，故考虑用线段树维护距中心为某个值的点的颜色。

设节点 $i$ 维护的范围为 $[l_i,r_i]$，则区域面积 $len_i=r_i^2-(l_i-1)^2$，另维护 $sum_i$ 表示在 $[l_i,r_i]$ 中黑色区域的总面积，$tag_i$ 表示区间 $[l_i,r_i]$ 是否要整体取反（合并和初始化要用的）。

一开始对 $rt_i$ 打 $[1,\frac{a_i}2]$ 的区间反转（置为黑色）。

进行合并时，叶子节点的值为 $sum_u\oplus sum_v$ （$\oplus$ 表示异或），代价等于 $[sum_u>0 \land sum_v>0]\times len_i$（只有两者都为黑才会产生 $len$ 的代价），非叶子节点递归合并。

然后你就愉快地 TLE 了……

为神马？

因为你的初始点数可能是满的，每次合并可以退化到 $O(n)$。

但是我们发现，如果这个区间内的所有数都是同一个值，那我们可以直接合并然后取反，就像这样：

if(tr[u].sum==tr[u].len){
    int res=tr[v].sum;
    pusht(v,1);
    return{v,res};
}

这样相当于每棵树初始只有 $O(\log n)$ 个点，合并 $n$ 次复杂度正确。

哦对了，不要忘记 pushdown，而且由于新建了 $n-1$ 棵树，rt 数组要开 $2n$。

没了，代码：

#include<iostream>
#include<cassert>
#include<algorithm>
#include<vector>
#define int long long
#define endl '\n'
#ifdef ONLINE_JUDGE
#define getc getc_unlocked
#endif
#define str stdin
using namespace std;

inline void read(int&x){
	x=0;
	int f=1;
	char ch=getc(str);
	while(ch<'0'||'9'<ch){
		if(ch=='-')f=-1;
		ch=getc(str);
	}
	while('0'<=ch&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getc(str);
	}
	x*=f;
}

namespace segtree{
	struct node{
		int ls,rs,sum,len,tag;
	};
	node tr[13000005];
	int tot;
	inline void update(int p){
		tr[p].sum=tr[tr[p].ls].sum+tr[tr[p].rs].sum;
	}
	inline void pusht(int p,int k){
		tr[p].sum=tr[p].len-tr[p].sum;
		tr[p].tag^=k;
	}
	inline void pushdown(int p){
		int ls=tr[p].ls,rs=tr[p].rs;
		if(tr[p].tag){
			pusht(ls,tr[p].tag);
			pusht(rs,tr[p].tag);
			tr[p].tag=0;
		}
	}
	int nnd(int l,int r){
		int p=++tot;
		tr[p].len=r*r-(l-1)*(l-1);
		return p;
	}
	void modify(int&p,int x,int y,int l,int r,int k){
		if(!p)p=nnd(l,r);
		if(x<=l&&r<=y){
			pusht(p,k);
			return;
		}
		int mid=(l+r)>>1;
		if(!tr[p].ls)tr[p].ls=nnd(l,mid);
		if(!tr[p].rs)tr[p].rs=nnd(mid+1,r);
		pushdown(p);
		if(x<=mid)modify(tr[p].ls,x,y,l,mid,k);
		if(mid<y)modify(tr[p].rs,x,y,mid+1,r,k);
		update(p);
	}
	pair<int,int>merge(int u,int v,int l,int r){
	//	cerr<<u<<' '<<v<<' '<<l<<' '<<r<<endl;
		if(!u||!v)return{u|v,0};
		if(!tr[u].sum)return{v,0};
		if(!tr[v].sum)return{u,0};
		if(tr[u].sum==tr[u].len){
			int res=tr[v].sum;
	//		cerr<<tr[u].sum<<' '<<tr[u].len<<' '<<res<<endl<<flush;
			pusht(v,1);
	//		cerr<<tr[v].sum<<endl<<flush;
			return{v,res};
		}
		if(tr[v].sum==tr[v].len){
			int res=tr[u].sum;
	//		cerr<<tr[v].sum<<' '<<tr[v].len<<' '<<res<<endl<<flush;
			pusht(u,1);
	//		cerr<<tr[u].sum<<endl<<flush;
			return{u,res};
		}
		if(l==r){
			int res=(tr[u].sum&&tr[v].sum)*tr[u].len;
	//		cerr<<tr[u].sum<<' '<<tr[v].sum<<' '<<tr[u].len<<' '<<res<<endl;
			tr[u].sum^=tr[v].sum;
			return {u,res};
		}
		int mid=(l+r)>>1;
//		if(!tr[u].ls)tr[u].ls=nnd(l,mid);
//		if(!tr[v].ls)tr[v].ls=nnd(l,mid);
//		if(!tr[u].rs)tr[u].rs=nnd(mid+1,r);
//		if(!tr[v].rs)tr[v].rs=nnd(mid+1,r);
		pushdown(u);pushdown(v);
		int res=0;
		pair<int,int>tmp=merge(tr[u].ls,tr[v].ls,l,mid);
		tr[u].ls=tmp.first,res+=tmp.second;
		tmp=merge(tr[u].rs,tr[v].rs,mid+1,r);
		tr[u].rs=tmp.first,res+=tmp.second;
		update(u);
		return {u,res};
	}
}
int rt[200005],a[100005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("P10834_4.in","r",stdin);
//	freopen("P10834_4.out","w",stdout);
	int n;
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
		a[i]/=2;
		segtree::modify(rt[i],1,a[i],1,5e5,1);
	}
	for(int i=1;i<n;i++){
		int x,y;
		read(x);read(y);
		pair<int,int>tmp=segtree::merge(rt[x],rt[y],1,5e5);
		rt[i+n]=tmp.first;
//		cerr<<"MERGE "<<i<<" COMPLETED\n"<<flush;
		cout<<tmp.second*4<<endl;
//		cerr<<i<<endl<<flush;
//		cout<<flush;
	}
	return 0;
}