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%的人