线段树合并

本文转载自https://blog.csdn.net/hongkongreporter/article/details/107116155并对部分内容进行了补充

总览：

动态开点线段树，像暴力的合并（然而不是
时间复杂度：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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

复杂度证明：

对于两颗有k个叶节点重合的线段树，合并的复杂度为klogm，合并之后会减少k个叶节点

也就是说每删除一个叶节点的复杂度是logm

对于n次操作，我们会产生n个叶节点，因此最多删除n个叶节点，复杂度就是nlogm

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;
}

  • 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

T2 P1600 天天爱跑步

思路：
先将路径拆成 s 到 lca 和 lca 到 t 两部分
对于 s 到 lca：
对 i 有贡献，当且仅当
dep_s-dep_i=w_i\\dep_i+w_i=dep_s

对于 lca 到 t：
对 i 有贡献，当且仅当
dep_s-dep_{lca}+dep_i-dep_{lca}=w_i\\dep_s-2\times dep_{lca}=w_i-dep_i
注意可能产生负数

线段树合并维护即可

代码：

#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;
}

  • 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

评论

发表评论

此博客中的热门博文