Reincarnation

正因为梦易碎，才格外美好。

全局平衡二叉树

发表于 更新于 分类于 ，
本文字数： 11k 阅读时长 ≈ 10 分钟

棋手关注的从来都不是棋子，而是那个与他对立而坐的，另一个棋手。

观前提醒/更新日志

前置知识：动态动态规划，树链剖分，，。

起稿。

后日谈ddp

记得很早之前做过的洛谷上的动态 的模板题，以及一小部分例题，却发现其加强版是无法通过的，因为树剖维护矩乘是一个 的过程，而那一道题的要求复杂度是一支 。

而这类题有一个较为普遍的做法，那就是用 ，但是 的常数极其大，甚至跑不过树剖的两支 ，所以我们考虑进行一些优化。

全局平衡二叉树

对此，存在两种理解：

  • 在树链剖分的基础上，对每一条链以相对平衡的方式重构一棵固态二叉树。
  • 在 的基础上，将 替换为全局平衡的二叉树。

如果某一个子树的轻儿子过多，则就会出现跳链多次的情况，也就是对于 条链都要执行 的查询，然后变成妥妥的两支 ，考虑一种 的抬浅操作，也就是在 中讲到的有关维护一支 的方法，让跳链的操作尽可能少即可。

但是一般而言，动态 维护的是静态树型结构，所以可以直接构造一棵平衡二叉树（相当于线段树），而不必要建立 ，用维护线段树的方法去维护这个静态的 即可。

我们在重新划分重链的时候，讲求“尽量均分”的原则，可以钦定为重链上的带权重心，最终目的是使链深度最小化，类似即可。

这样下来，即使是使用树剖在维护，但实质是 ，但又没有 的巨大常数，所以是 ，在链时达到极值。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// ----- Eternally question-----
// Problem: P4751 【模板】"动态DP"&动态树分治（加强版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4751
// Memory Limit: 250 MB
// Time Limit: 3500 ms
// Written by: Eternity
// Time: 2022-11-17 11:15:33
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned uint;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define ls(p) Chi[p][0]
#define rs(p) Chi[p][1]
const int MAXN=1e6+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
uint N,Q;
struct Matrix
{
	ll a[2][2];
	Matrix():a{{-INF,-INF},{-INF,-INF}}{};
	ll*operator[](int x){ return a[x]; }
	friend Matrix operator*(Matrix a,Matrix b)
	{
		Matrix ans;
		for(int i=0;i<2;++i) for(int j=0;j<2;++j)
			for(int k=0;k<2;++k) checkMax(ans[i][k],a[i][j]+b[j][k]);
		return ans;
	}
};
uint Fa[MAXN],Chi[MAXN][2];
std::vector<uint>Edges[MAXN];
uint Siz[MAXN],Son[MAXN],Sizs[MAXN];
void dfsTree(uint x,uint last)
{
	Siz[x]=1,Fa[x]=last,Son[x]=-1;
	for(auto v:Edges[x])
	{
		if(v==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(!~Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
	Sizs[x]=Siz[x];
	if(~Son[x]) Sizs[x]-=Siz[Son[x]];
}
ll g[MAXN],h[MAXN],v[MAXN];
Matrix Val[MAXN];
inline void pushUp(uint p)
{
	Val[p][0][0]=Val[p][0][1]=g[p];
	Val[p][1][0]=h[p],Val[p][1][1]=-INF;
	if(~ls(p)) Val[p]=Val[ls(p)]*Val[p];
	if(~rs(p)) Val[p]=Val[p]*Val[rs(p)];
}
uint build(uint l,uint r,std::vector<uint>&ps)
{
	if(l>=r) return -1;
	uint siz=0,wgt=-1,pos=l;
	for(uint i=l;i<r;++i) siz+=Sizs[ps[i]];
	for(uint i=l,s=0;i<r;++i)
	{
		uint a=std::max(s,siz-s-Sizs[ps[i]]);
		if(checkMin(wgt,a)) pos=i;
		s+=Sizs[ps[i]];
	}
	if(~(ls(ps[pos])=build(l,pos,ps))) Fa[ls(ps[pos])]=ps[pos];
	if(~(rs(ps[pos])=build(pos+1,r,ps))) Fa[rs(ps[pos])]=ps[pos];
	pushUp(ps[pos]);
	return ps[pos];
}
uint build(uint p)
{
	std::vector<uint>vec;
	while(~p) vec.push_back(p),p=Son[p];
	for(auto x:vec) for(auto v:Edges[x])
	{
		if(v==Fa[x]||v==Son[x]) continue;
		uint pos=build(v);Fa[pos]=x;
		g[x]+=std::max(Val[pos][0][0],Val[pos][1][0]),h[x]+=Val[pos][0][0];
	}
	return build(0,vec.size(),vec);
}
inline void remove(uint p)
{
	while(~p)
	{
		if(~Fa[p]&&p!=ls(Fa[p])&&p!=rs(Fa[p]))
			g[Fa[p]]-=std::max(Val[p][0][0],Val[p][1][0]),h[Fa[p]]-=Val[p][0][0];
		p=Fa[p];
	}
}
inline void upDate(uint p)
{
	while(~p)
	{
		pushUp(p);
		if(~Fa[p]&&p!=ls(Fa[p])&&p!=rs(Fa[p]))
			g[Fa[p]]+=std::max(Val[p][0][0],Val[p][1][0]),h[Fa[p]]+=Val[p][0][0];
		p=Fa[p];
	}
}
int main()	
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q);
	for(uint i=0;i<N;++i) read(v[i]),h[i]=v[i];
	for(uint i=2,u,v;i<=N;++i){ read(u,v);Edges[--u].push_back(--v),Edges[v].push_back(u); }
	dfsTree(0,-1);
	uint Rt=build(0);Fa[Rt]=-1;
	ll lastans=0;
	for(uint qx;Q--;)
	{
		ll qv;read(qx,qv),qx^=lastans;--qx;
		remove(qx);
		h[qx]-=v[qx],h[qx]+=v[qx]=qv;
		upDate(qx);
		write(lastans=std::max(Val[Rt][0][0],Val[Rt][1][0]),'\n');
	}
	return 0;
}
/*

*/

例题

全局平衡与多项式卷积

题目简介

题目名称：切树游戏
题目来源：山东省选 第一天第三题

评测链接：https://www.luogu.com.cn/problem/P3781

形式化题意：给定一棵有 个结点的点权树，有 次操作形如：

  1. 将 结点的点权修改为 ；
  2. 求异或和为 的连通块个数。

数据范围：

全局平衡与构造

题目简介

题目名称：

题目来源： 第二天第一题

评测链接 ：https://loj.ac/p/3816
评测链接 ：https://www.luogu.com.cn/problem/P8999

形式化题意：一个平面上有 个点 ，将这 个点映射至一棵大小为 的树上，要求将树上结点 的边映射为平面上两两结点之间的线段，要求构造一组映射使得两两线段不交。

数据范围：

首先考虑在 的时间内求解：定下树根 ，设当前坐标集合为 ，以 对应的位置为中心进行极角排序，按 的子树大小切割连续段 ，并依次分配给 的 棵子树，每个子树的根对应 中极角最靠前的，递归求解即可。用 std::nth_element 可以省去排序的一支 。

对于优化，我们需要得到的是，让当前分治区间的连通块不会与块外已经决策结束的结点发生冲突，而保证的条件就是，我们用很多的点去划分了边界，而边界点对决策干扰很大，所以我们现在要得到一个用较少点去决定区间的方法。

考虑一种方法使每一次分治区间减半，如果将分治中心（边界点）选择为直径的两个端点，分配凸包上的两个相邻结点开始分治，并找到中点，划分出一个不包含任何结点的三角形，当分支中心相邻时，在连通块中找到距其最远的结点作为连接点，再分配另一个相邻点到凸包上即可，用长链剖分维护为 。

考虑重剖，取重心代替直径，复杂度优化成 。然后每一次取分治中心取为加权中点，并让两边尽可能平衡，用全局平衡二叉树分治，配合题目给定的三度化，复杂度就可以在 内解决了。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// ----- Eternally question-----
// Problem: #3816. 「CEOI2022」Drawing
// Contest: LibreOJ
// URL: https://loj.ac/p/3816
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// Written by: Eternity
// Time: 2023-04-07 20:42:51
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
struct Vec
{
	ll x,y;
	inline Vec(ll u,ll v):x(u),y(v){};
	Vec operator-(const Vec v) const
	{ return Vec(x-v.x,y-v.y); }
}O=Vec(-1,-1);
const ll cross(Vec u,Vec v){ return u.x*v.y-u.y*v.x; }
struct Node
{int x,y,id;}Mp[MAXN];
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Total;
int N,Rt,In[MAXN],Siz[MAXN],ans[MAXN],Son[MAXN];
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;++In[u];
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;++In[v];
}
inline bool cmp(Node &u,Node &v)
{ return cross(Vec(u.x,u.y)-O,Vec(v.x,v.y)-O)>0; }
void dfsTree(int x,int last)
{
	Siz[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
}
void solve(int u,std::vector<Node>& a);
void Dac(int l,int r,std::vector<Node>&a,std::vector<int>&b)
{
	if(l+1>=r)
	{
		if(!a.size()) return ;
		int u=b[l],v;
		for(int e=Head[u];e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(v!=b[r]&&Siz[v]<Siz[u]) break;
		}
		O=Vec(Mp[u].x,Mp[u].y);
		std::nth_element(a.begin(),a.begin(),a.end(),cmp);
		solve(v,a);return ;
	}
	int mid=(Siz[b[l]]-Siz[b[r]])>>1,sl=0,Mid;
	for(int i=l;i<=r;++i){
		sl+=Siz[b[i]]-Siz[b[i+1]];
		if(i>l&&sl>mid){Mid=i;break;}
	}
	sl=Siz[b[l]]-Siz[b[Mid]]-1;
	std::vector<Node> L;
	O=Vec(Mp[b[l]].x,Mp[b[l]].y);
	std::nth_element(a.begin(),a.begin()+sl,a.end(),cmp);
	O=Vec(Mp[b[r]].x,Mp[b[r]].y);
	std::nth_element(a.begin()+sl,a.begin()+sl,a.end(),cmp);
	for(int i=0;i<sl;++i)
	{
		if(cmp(a[i],a[sl])) L.push_back(a[i]);
		else a.push_back(a[i]);
	}
	Mp[b[Mid]]=a[sl];
	O=Vec(a[sl].x,a[sl].y);
	a.erase(a.begin(),a.begin()+sl+1); 
	if((sl-=L.size())>0)
	{
		nth_element(a.begin(),a.begin()+sl-1,a.end(),cmp);
		L.insert(L.end(),a.begin(),a.begin()+sl);
		a.erase(a.begin(),a.begin()+sl);
	}
	Dac(l,Mid,L,b);Dac(Mid,r,a,b);
}
void solve(int u,std::vector<Node>& a)
{
	Mp[u]=*a.begin();a.erase(a.begin());
	O=Vec(Mp[u].x,Mp[u].y);
	if(!a.size()) return ;
	std::nth_element(a.begin(),a.end()-1,a.end(),cmp);
	std::vector<int>b;
	while(u) b.push_back(u),u=Son[u];
	Mp[b.back()]=a.back();
	a.pop_back();
	Dac(0,b.size()-1,a,b);
}
int main()
{
	read(N);std::vector<Node>a;
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
	for(int i=1,u,v;i<=N;++i) read(u,v),a.push_back((Node){u,v,i});
	for(int i=1;i<=N;++i) if(In[i]<=1){ Rt=i;break; }
	dfsTree(Rt,0);
	std::nth_element(a.begin(),a.begin(),a.end(),cmp);
	solve(Rt,a);
	for(int i=1;i<=N;++i) ans[Mp[i].id]=i;
	for(int i=1;i<=N;++i) write(ans[i],' ');
}
/*

*/
相关文章