20200703 專題：線段樹合并

總覽：

動态開點線段樹，像暴力的合并（然而不是

時間複雜度： O ( n l o g n ) O(nlogn) O(nlogn)

模闆：

inline int merge(int x,int y,int l,int r){
	if(!x||!y)	return x|y;
	if(l==r){
		//将y合并到x
		return x;
	}
	int mid=(l+r)>>1;
	tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);
	tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
	pushup(x);
	return x;
}

如果需要可持久化，可以動态開點

T1 P4556 [Vani有約會]雨天的尾巴 /【模闆】線段樹合并

思路：

差分

在 x,y 處加，lca(x,y),f(lca(x,y)) 處減

從葉子結點開始合并查詢

代碼：

#include <bits/stdc++.h>
using namespace std;
#define re register
namespace IO {
#define in Read()
inline char ch() {
  static char buf[1 << 21], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int in {
  int s = 0, f = 1;
  char x;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = getchar())
    s = (s << 1) + (s << 3) + (x & 15);
  return f == 1 ? s : -s;
}
}  // namespace IO
using namespace IO;

const int A=4e5+5;
const int K=1e5;
int n,m;
int head[A],tot_road;
struct Road{
	int nex,to;
}road[2*A];
inline void edge(int x,int y){
	road[++tot_road]={head[x],y};head[x]=tot_road;
}
int dep[A],f[A],top[A],son[A],sz[A];

inline void DFS1(int fa,int x){
	f[x]=fa,dep[x]=dep[fa]+1,sz[x]=1;
	for(int y=head[x];y;y=road[y].nex){
		int z=road[y].to;
		if(z==fa)	continue;
		DFS1(x,z);
		sz[x]+=sz[z];
		if(sz[z]>sz[son[x]])	son[x]=z;
	}
	return;
}

inline void DFS2(int x){
	if(son[x]){
		top[son[x]]=top[x];
		DFS2(son[x]);
	}
	for(int y=head[x];y;y=road[y].nex){
		int z=road[y].to;
		if(top[z])	continue;
		top[z]=z;
		DFS2(z);
	}
	return;
}

inline void tree_cut(){
	DFS1(0,1);
	top[1]=1;
	DFS2(1);
	return;
}

inline int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])	swap(x,y);
		x=f[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}

int rt[A],tot;
struct Tree{
	int ls,rs,num,ans;
}tr[20*A];
int res[A];

inline void pushup(int x){
	if(tr[tr[x].ls].num<=0&&tr[tr[x].rs].num<=0)	return;
	if(tr[tr[x].ls].num>=tr[tr[x].rs].num){
		tr[x].num=tr[tr[x].ls].num;
		tr[x].ans=tr[tr[x].ls].ans;
	}
	else{
		tr[x].num=tr[tr[x].rs].num;
		tr[x].ans=tr[tr[x].rs].ans;
	}
	return;
}

inline void add(int &x,int l,int r,int w,int val){
	if(!x)	x=++tot;
	if(l==r){
		tr[x].num+=val;
		tr[x].ans=tr[x].num>0?l:0;
		return;
	}
	int mid=(l+r)>>1;
	if(w<=mid)	add(tr[x].ls,l,mid,w,val);
	else	add(tr[x].rs,mid+1,r,w,val);
	pushup(x);
	return;
}

inline int merge(int x,int y,int l,int r){
	if(!x||!y)	return x|y;
	if(l==r){
		tr[x].num+=tr[y].num;
		tr[x].ans=tr[x].num>0?l:0;
		return x;
	}
	int mid=(l+r)>>1;
	tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);
	tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
	pushup(x);
	return x;
}

inline void work(int fa,int x){
	for(int y=head[x];y;y=road[y].nex){
		int z=road[y].to;
		if(z==fa)	continue;
		work(x,z);
		rt[x]=merge(rt[x],rt[z],1,K);
	}
	res[x]=tr[rt[x]].ans;
	return;
}

signed main() {
	n=in,m=in;
	for(int i=1;i<n;i++){
		int u=in,v=in;
		edge(u,v),edge(v,u);
	}
	tree_cut();
	for(int i=1;i<=m;i++){
		int u=in,v=in,w=in;
		add(rt[u],1,K,w,1);
		add(rt[v],1,K,w,1);
		add(rt[lca(u,v)],1,K,w,-1);
		add(rt[f[lca(u,v)]],1,K,w,-1);
	}
	work(0,1);
	for(int i=1;i<=n;i++)
		printf("%d\n",res[i]);
  return 0;
}

T2 P1600 天天愛跑步

思路：

先将路徑拆成 s 到 lca 和 lca 到 t 兩部分

對于 s 到 lca：

對 i 有貢獻，當且僅當

d e p s − d e p i = w i d e p i + w i = d e p s dep_s-dep_i=w_i\\ dep_i+w_i=dep_s deps−depi=widepi+wi=deps

對于 lca 到 t：

對 i 有貢獻，當且僅當

d e p s − d e p l c a + d e p i − d e p l c a = w i d e p s − 2 × d e p l c a = w i − d e p i dep_s-dep_{lca}+dep_i-dep_{lca}=w_i\\ dep_s-2\times dep_{lca}=w_i-dep_i deps−deplca+depi−deplca=wideps−2×deplca=wi−depi

注意可能産生負數

線段樹合并維護即可

代碼：

#include <bits/stdc++.h>
using namespace std;
#define re register
namespace IO {
#define in Read()
inline char ch() {
  static char buf[1 << 21], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int in {
  int s = 0, f = 1;
  char x;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = getchar())
    s = (s << 1) + (s << 3) + (x & 15);
  return f == 1 ? s : -s;
}
}  // namespace IO
using namespace IO;

const int A=3e5+5;
const int K=3e5;
int n,m;
int head[A],tot_road;
struct Road{
	int nex,to;
}road[2*A];
inline void edge(int x,int y){
	road[++tot_road]={head[x],y};head[x]=tot_road;
}
int f[A],dep[A],sz[A],son[A],top[A];

inline void DFS1(int fa,int x){
	f[x]=fa,dep[x]=dep[fa]+1,sz[x]=1;
	for(int y=head[x];y;y=road[y].nex){
		int z=road[y].to;
		if(z==fa)	continue;
		DFS1(x,z);
		sz[x]+=sz[z];
		if(sz[z]>sz[son[x]])	son[x]=z;
	}
	return;
}

inline void DFS2(int x){
	if(son[x]){
		top[son[x]]=top[x];
		DFS2(son[x]);
	}
	for(int y=head[x];y;y=road[y].nex){
		int z=road[y].to;
		if(top[z])	continue;
		top[z]=z;
		DFS2(z);
	}
	return;
}

inline void tree_cut(){
	DFS1(0,1);
	top[1]=1;
	DFS2(1);
	return;
}

inline int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])	swap(x,y);
		x=f[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}

int tim[A];
int rt[A],tot;
struct Tree{
	int ls,rs,s[2];
}tr[20*A];
int res[A];

inline void pushup(int x){
	if(!tr[x].ls&&!tr[x].rs)	return;
	tr[x].s[0]=tr[tr[x].ls].s[0]+tr[tr[x].rs].s[0];
	tr[x].s[1]=tr[tr[x].ls].s[1]+tr[tr[x].rs].s[1];
	return;
}

inline void add(int &x,int l,int r,int w,int val,int pos){
	if(!x)	x=++tot;
	if(l==r){
		tr[x].s[pos]+=val;
		return;
	}
	int mid=(l+r)>>1;
	if(w<=mid)	add(tr[x].ls,l,mid,w,val,pos);
	else	add(tr[x].rs,mid+1,r,w,val,pos);
	pushup(x);
	return;
}

inline int merge(int x,int y,int l,int r){
	if(!x||!y)	return x|y;
	if(l==r){
		tr[x].s[0]+=tr[y].s[0];
		tr[x].s[1]+=tr[y].s[1];
		return x;
	}
	int mid=(l+r)>>1;
	tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);
	tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
	pushup(x);
	return x;
}

inline int qurey(int x,int l,int r,int w,int pos){
	if(!x)	return 0;
	if(l==r)	return tr[x].s[pos];
	int mid=(l+r)>>1;
	if(w<=mid)	return qurey(tr[x].ls,l,mid,w,pos);
	else	return qurey(tr[x].rs,mid+1,r,w,pos);
}

inline void work(int fa,int x){
	for(int y=head[x];y;y=road[y].nex){
		int z=road[y].to;
		if(z==fa)	continue;
		work(x,z);
		rt[x]=merge(rt[x],rt[z],-K,K);
	}
	res[x]+=qurey(rt[x],-K,K,dep[x]+tim[x],0);
	res[x]+=qurey(rt[x],-K,K,tim[x]-dep[x],1);
	return;
}

signed main() {
	n=in,m=in;
	for(int i=1;i<n;i++){
		int u=in,v=in;
		edge(u,v),edge(v,u);
	}
	tree_cut();
	for(int i=1;i<=n;i++)	tim[i]=in;
	for(int i=1;i<=m;i++){
		int u=in,v=in;
		int k=lca(u,v);
		add(rt[u],-K,K,dep[u],1,0);
		add(rt[f[k]],-K,K,dep[u],-1,0);
		add(rt[v],-K,K,dep[u]-2*dep[k],1,1);
		add(rt[k],-K,K,dep[u]-2*dep[k],-1,1);
	}
	work(0,1);
	for(int i=1;i<=n;i++)	printf("%d ",res[i]);
  return 0;
}

20200703 專題：線段樹合并

總覽：

T1 P4556 [Vani有約會]雨天的尾巴 /【模闆】線段樹合并

T2 P1600 天天愛跑步

繼續閱讀

WPF 中的window 窗體

2018.08.15 bzoj3747: [POI2015]Kinoman（線段樹）

氪周刊：關注網際網路創業

《大資料，小時代，向移動網際網路遷徙-2012上半年移動網際網路資料分享》_DCCI

Linux運維趨勢：阿裡運維監控那些事兒

洛谷P3372 【模闆】線段樹 1題目大意題目分析 C o d e Code Code

Windows環境下32位彙編語言程式設計

2019.07.09【NOIP提高組】模拟 A 組比賽總結題目總結CODE

2019.07.11【NOIP提高組】模拟 A 組&B組總結A組總結CODE

2019.08.07【NOIP提高組】模拟 A 組比賽總結題目總結題解CODE

2020.11.05【NOIP提高A組】模拟比賽總結比賽位址題目總結CODE

20200804 專題：仙人掌（圓方樹）

【loj6092】【雅禮集訓 2017 Day1】市場（線段樹）

2018.07.08 POJ 2481 Cows（線段樹）

reflect metadata & dependency injection

【LeetCode013算法/程式設計練習C++】Roman to Integer //難得擊敗了80%的人