专栏文章

[COTS 2023] 题 Zadatak

ppig1121
P10834题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqoz30m
此快照首次捕获于
2025/12/04 08:22
3 个月前
此快照最后确认于
2025/12/04 08:22
3 个月前
查看原文
考虑线段树合并。
先试图用线段树表示状态。注意到合并是中心对齐且 2∣ai2\mid a_i，故只需要维护正方形的一角（输出时将答案乘以 44）。某一个位置的颜色只与它到中心的水平（或竖直）距离有关，故考虑用线段树维护距中心为某个值的点的颜色。
设节点 ii 维护的范围为 [li,ri][l_i,r_i]，则区域面积 leni=ri2−(li−1)2len_i=r_i^2-(l_i-1)^2，另维护 sumisum_i 表示在 [li,ri][l_i,r_i] 中黑色区域的总面积，tagitag_i 表示区间 [li,ri][l_i,r_i] 是否要整体取反（合并和初始化要用的）。
一开始对 rtirt_i 打 [1,ai2][1,\frac{a_i}2] 的区间反转（置为黑色）。
进行合并时，叶子节点的值为 sumu⊕sumvsum_u\oplus sum_v （⊕\oplus 表示异或），代价等于 [sumu>0∧sumv>0]×leni[sum_u>0 \land sum_v>0]\times len_i（只有两者都为黑才会产生 lenlen 的代价），非叶子节点递归合并。
然后你就愉快地 TLE 了……
为神马？
因为你的初始点数可能是满的，每次合并可以退化到 O(n)O(n)。
但是我们发现，如果这个区间内的所有数都是同一个值，那我们可以直接合并然后取反，就像这样：
CPP
if(tr[u].sum==tr[u].len){
    int res=tr[v].sum;
    pusht(v,1);
    return{v,res};
}
这样相当于每棵树初始只有 O(log⁡n)O(\log n) 个点，合并 nn 次复杂度正确。
哦对了，不要忘记 pushdown，而且由于新建了 n−1n-1 棵树，rt 数组要开 2n2n。
没了，代码：
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...