数据结构选讲（更新中）

参考 smWCDay7 数据结构选讲2 by yyc 。

可能会补充的：

AT_cf17_final_j TreeMST 的 F2 Boruvka算法

AT_cf17_final_j Tree MST

link
题意
给定一棵 $n$ 个点的树，点有点权 $w_i$ ，边有边权。建立一张完全图 $G$ ，节点 $u, v$ 之间的边长为 $w_u + w_v + dis(u, v)$ 。求 $G$ 的 $MST$ （最小生成树）的边权和。

$\le 2 \times 10^5 ，1 \le w_i \le 10^9$

思路
前置指示：点分治

引理：边 $e$ 在边集 $E$ 的最小生成树中，则对于任意 $E_0 ⊆ E$ ，e 也在边集 $E_0$ 的最小生成树中。
证明：考虑 kruskal。
推论：将边分为若干组，分别求最小生成树，再合并求最小生成树，结果正确。

题目是说建立一张完全图然后求其的 $MST$ ,但是这样的边是 $n^2$ 级别的，考虑去掉一些多余的边，只保留有用的边。所以可以将完全图 $G$ 分成很多个边集，分别求 $MST$ （不必强制联通），然后保留有用边，最后再综合求 $MST$ 就是答案了。
考虑 点分治，以重心为根，将树分成几个子树，那么就只用处理跨越重心的边即可。
记 $dis_i$ 表示点 $i$ 到重心的距离，跨越重心的边 $(u, v)$ ，边权是 $w_u + dis_u + w_v + dis_v$ 。由于每个点 $i$ 都要贡献至少一次 $w_i+dis_i$ ，另外一边肯定选最小的 $w_j+dis_j$ ，所以我们只需要选择 $w_i + dis_i$ 最小的点，让它和所有其他点连边，该菊花图就是最小生成树。（在同一棵子树内连了边也不影响结果，因为它们的边权比真实值要大 $dis_u + dis_v \gt dis_{u,v}$ ）。这样边的数量就减到了 $n l o g n$ ，总时间复杂度为 $O(nlog^2n)$ 。

好像还有一种方法，要用到 Boruvka算法 ，后续可能会学……

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;

int idx,head[maxn];
struct EDGE{ int v,next; ll w; }e[maxn*2];
void Insert(int u,int v,ll w){
	e[++idx]={v,head[u],w};
	head[u]=idx;
}

int siz[maxn],mxson[maxn],pot[maxn],tn;
bool vis[maxn];
void Dfs(int x,int fa){
	pot[++tn]=x,siz[x]=1,mxson[x]=0;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(!vis[v]&&v!=fa){
			Dfs(v,x);
			siz[x]+=siz[v];
			mxson[x]=max(mxson[x],siz[v]);
		}
	}
}

int Get_root(int x){
	tn=0,Dfs(x,0);
	int root=0;
	for(int i=1;i<=tn;i++){
		mxson[pot[i]]=max(mxson[pot[i]],tn-siz[pot[i]]);
		if(!root||mxson[root]>mxson[pot[i]]) root=pot[i]; 
	}
	return root;
}

int id;
ll a[maxn],dis[maxn];
void Dfs2(int x,int fa){
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(!vis[v]&&v!=fa){
			dis[v]=dis[x]+e[i].w;
			Dfs2(v,x);
		}
	}
	if(!id||a[x]+dis[x]<a[id]+dis[id]) id=x;
}

int cnt;
struct EDGE2{ int u,v; ll w; }te[maxn*20];
void Solve(int rt){
	dis[rt]=0,id=0,Dfs2(rt,0);
	for(int i=1;i<=tn;i++)
		te[++cnt]={id,pot[i],a[id]+dis[id]+a[pot[i]]+dis[pot[i]]};
	vis[rt]=1;
	for(int i=head[rt];i;i=e[i].next){
		int v=e[i].v;
		if(!vis[v]) Solve(Get_root(v));
	}
}

int fa[maxn];
int Find_fa(int x){ return fa[x]==x?x:fa[x]=Find_fa(fa[x]); }

int main(){
	int n; cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++){
		int x,y,z; cin>>x>>y>>z;
		Insert(x,y,z),Insert(y,x,z);
	}
	Solve(Get_root(1));
	sort(te+1,te+cnt+1,[](EDGE2 a,EDGE2 b){ return a.w<b.w; });
	for(int i=1;i<=n;i++)
		fa[i]=i;
	ll ans=0;
	for(int i=1;i<=cnt;i++){
		int fx=Find_fa(te[i].u),fy=Find_fa(te[i].v);
		if(fx!=fy) fa[fy]=fx,ans+=te[i].w;
	}
	cout<<ans;
	return 0;
}

P5280 [ZJOI2019] 线段树

link
题意
维护线段树集合，初始时，集合中只有一棵 $[1, n]$ 的空线段树。支持下列操作：

将每棵线段树复制两份，其中一份执行区间覆盖。
查询目前所有线段树中，有标记的节点个数。
$\le 10^5$

思路
看到题目，可以想到：线段树的个数是指数级别的，不可能单独地去维护每一棵线段树，但每棵线段树都是相同的，思考是否可以去用一棵线段树来维护，每次修改在上一次的基础上进行转移。又发现一次修改中，不同的点的转移是不同的。
那就观察点的修改，总共可以分成五类：

白色：在 Modify 操作中，被半覆盖的点；
深灰色：在 Modify 操作中，被全覆盖的点，并且能被遍历到；
橙色：在 Modify 操作中，未被覆盖的点，并且可能可以得到 pushdown 来的标记；
浅灰色：在 Modify 操作中，被全覆盖的点，并且不能被遍历到（深灰色点的儿子）；
黄色：在 Modify 操作中，未被覆盖的点，并且不可能得到 pushdown 来的标记（橙色点的儿子）；

设个 $D P$ 观察五种点的转移：记 $f_{i,u}$ 表示到第 $i$ 次 Modify 操作时，在 $2^i$ 棵树中，点 $u$ 被打了标记的个数； $g_{i,u}$ 表示到第 $i$ 次 Modify 操作时，在 $2^i$ 棵树中，有多少棵树满足根到结点 $u$ 的路径上的点至少有一个标记。
转移如下：

白色： $f_{i,u} = f_{i−1,u}$ ， $g_{i,u} = g_{i−1,u}$
深灰色： $f_{i,u} = f_{i−1,u} + 2^{i-1}$ ， $g_{i,u} = g_{i−1,u} + 2^{i-1}$
橙色： $f_{i,u} = f_{i−1,u} + g_{i-1,u}$ ， $g_{i,u} = 2 \times g_{i−1,u}$
浅灰色： $f_{i,u} = 2 \times f_{i−1,u}$ ， $g_{i,u} = g_{i−1,u} + 2^{i-1}$
黄色： $f_{i,u} = 2 \times f_{i−1,u}$ ， $g_{i,u} = 2 \times g_{i−1,u}$

每次修改暴力转移每个点是不可能的。但每次的白色，深灰色，橙色只有 $O (l o g n)$ 个，可以暴力；浅灰色和黄色有 $O (n)$ 个，可以用懒标记维护。还要维护 $sum_u$ 表示 $u$ 子树中 $f_u$ 的总和， $sum_1$ 就是答案。
维护转移时有点细节（懒标记），注意多 $p u s h d o w n$ 标记。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5,mod=998244353;

struct TREE{ ll f,g,tagf,tagg,tagg2,sum; }tree[maxn*4];
void Build(int rt,int l,int r){
	tree[rt].tagf=tree[rt].tagg2=1;
	if(l==r) return;
	int mid=(l+r)>>1;
	Build(rt*2,l,mid),Build(rt*2+1,mid+1,r);
}

void F_mul(int rt,ll k){ (tree[rt].f*=k)%=mod,(tree[rt].tagf*=k)%=mod,(tree[rt].sum*=k)%=mod; }
void G_add(int rt,ll k){ (tree[rt].g+=k)%=mod,(tree[rt].tagg+=k)%=mod; }
void G_mul(int rt,ll k){ (tree[rt].g*=k)%=mod,(tree[rt].tagg2*=k)%=mod,(tree[rt].tagg*=k)%=mod; }
void Pushdown(int rt){
	int ls=rt*2,rs=ls+1;
	if(tree[rt].tagf!=1) F_mul(ls,tree[rt].tagf),F_mul(rs,tree[rt].tagf),tree[rt].tagf=1;
	if(tree[rt].tagg2!=1) G_mul(ls,tree[rt].tagg2),G_mul(rs,tree[rt].tagg2),tree[rt].tagg2=1;
	if(tree[rt].tagg) G_add(ls,tree[rt].tagg),G_add(rs,tree[rt].tagg),tree[rt].tagg=0;
}
void Pushup(int rt){ tree[rt].sum=(tree[rt*2].sum+tree[rt*2+1].sum+tree[rt].f)%mod; }

void Modify(int rt,int l,int r,int x,int y,ll z){//white, deep_grey, light_grey
	if(x<=l&&r<=y){//deep_grey
		(tree[rt].f+=z)%=mod,(tree[rt].g+=z)%=mod;
		F_mul(rt*2,2),G_add(rt*2,z); F_mul(rt*2+1,2),G_add(rt*2+1,z);//light_grey
		Pushup(rt);
		return;
	}
	Pushdown(rt);
	int mid=(l+r)>>1;
	if(x<=mid) Modify(rt*2,l,mid,x,y,z);
	if(y>mid) Modify(rt*2+1,mid+1,r,x,y,z);
	Pushup(rt);
}

void Modify2(int rt,int l,int r,int x,int y){//orange, yello
	if(x<=l&&r<=y){//orange
		(tree[rt].f+=tree[rt].g)%=mod,(tree[rt].g*=2)%=mod;
		F_mul(rt*2,2),G_mul(rt*2,2); F_mul(rt*2+1,2),G_mul(rt*2+1,2);//yellow
		Pushup(rt);
		return;
	}
	Pushdown(rt);
	int mid=(l+r)>>1;
	if(x<=mid) Modify2(rt*2,l,mid,x,y);
	if(y>mid) Modify2(rt*2+1,mid+1,r,x,y);
	Pushup(rt);
}

ll pw[maxn];
int main(){
	int n,m; cin>>n>>m;
	pw[0]=1;
	for(int i=1;i<=m;i++)
		pw[i]=pw[i-1]*2%mod;
	Build(1,1,n);
	int cnt=0;
	while(m--){
		int opt; cin>>opt;
		if(opt==1){
			int x,y; cin>>x>>y; cnt++;
			Modify(1,1,n,x,y,pw[cnt-1]);
			if(x>1) Modify2(1,1,n,1,x-1);
			if(y<n) Modify2(1,1,n,y+1,n);
		}
		else cout<<tree[1].sum<<"\n";
	}
	return 0;
}