数据结构选讲（更新中）

参考 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_greyif(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_greyPushup(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, yelloif(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);//yellowPushup(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;
}