JZTXT

线段树合并

发布时间 2023-08-07 07:47:35作者: xishanmeigao

Part 1：知识点

  • 前置知识：动态开点线段树

  • 线段树合并是一个递归的过程。我们合并两棵线段树时，用两个指针 \(p,q\) 从两个根节点出发，以递归的方式同步遍历两棵线段树。

    1.若 \(p,q\) 之一为空，则以非空的那个作为合并的节点

    2.若 \(p,q\) 均不为空，则递归合并两棵左子树和两棵右子树，然后删除节点 \(q\)，以 \(p\) 为合并后的新节点，然后删除节点 \(q\)，以 \(p\) 作为合并后的节点，更新信息

  • 参考代码

int merge(int p,int q,int l,int r)
{
	if(!p)
	    return q;
	if(!q)
	    return p;
	
	if(l==r)
	{
	    dat(p)+=dat(q)
	    return p;
	}
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	pushup(p);
	
	return p;
}
  • 时间复杂度 & 空间复杂度： \(O(n\log n)\)

Part 2：练习题

【模板】线段树合并 / [Vani有约会] 雨天的尾巴

（题目传送门）

题目大意

首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x, y)\)，然后对于 \(x\) 到 \(y\) 的路径上（含 \(x\) 和 \(y\)）每座房子里发放一袋 \(z\) 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

解题思路

  • 根据套路，容易想到先找出 \(x,y\) 的最近公共祖先 \(lca\)，之后进行树上差分。设 \(b[z]\) 为差分数组，对于每次操作，令 \(b[z][x]+1\)，\(b[z][y]+1\)，\(b[z][lca]-1\)，\(b[z][fa[lca]]-1\) 即可。

  • 现在考虑优化，我们可以对每一个点建立一棵权值线段树来替代差分数组，维护存放最多的救济粮的类型和数量，之后从根节点开始进行一次 \(\mathrm{dfs}\)，对于 \(x\) 节点的所有儿子 \(y\)，将它们的线段树合并起来，即完成差分数组最后的求前缀和的过程

代码

#include<bits/stdc++.h>
using namespace std;

const int N=100010,M=100000;

struct SegmentTree
{
	int val,ki;
	int lc,rc;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc 
	#define val(x)  tree[x].val
	#define ki(x)  tree[x].ki
}tree[80*N];

int n,m,t;
int dep[N],f[N][20],tot;
int rt[N],ans[N];
vector <int> g[N];
queue <int> q;

void bfs()
{
	q.push(1);
	dep[1]=1;
	
	while(q.size())
	{
		int x=q.front();  q.pop();
		for(int i=0; i<g[x].size(); i++)
		{
			int y=g[x][i];
			if(dep[y])
				continue;
			
			dep[y]=dep[x]+1;
			f[y][0]=x;
			for(int j=1; j<=t; j++)
				f[y][j]=f[f[y][j-1]][j-1];
				
			q.push(y); 
		}
	}
}

int LCA(int x,int y)
{
	if(dep[x]>dep[y])
		swap(x,y);
	for(int i=t; i>=0; i--)
		if(dep[f[y][i]]>=dep[x])
			y=f[y][i];
			
	if(x==y)
		return x;
		
	for(int i=t; i>=0; i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	
	return f[x][0];
}

void pushup(int p)
{
	if(val(lc(p))>=val(rc(p)))
		val(p)=val(lc(p)),ki(p)=ki(lc(p));
	else
		val(p)=val(rc(p)),ki(p)=ki(rc(p));
}

void change(int &p,int l,int r,int pos,int v)
{
	if(!p)
		p=++tot;
		
	if(l==r)
	{
		val(p)+=v;
		ki(p)=pos;
		return; 
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v);
	else
		change(rc(p),mid+1,r,pos,v);
		
	pushup(p);
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
	
	if(l==r)
	{
		val(p)+=val(q);
		ki(p)=l;
		return p;
	}
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	pushup(p);
	
	return p;
}

void dfs(int x,int fa)
{
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		if(y==fa)
			continue;
		
		dfs(y,x);
		rt[x]=merge(rt[x],rt[y],1,M);
	}
	
	if(val(rt[x]))
		ans[x]=ki(rt[x]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<n; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	t=(log(n)/log(2))+1;
	bfs();
	
	for(int i=1; i<=m; i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		
		int lca=LCA(x,y);
		
		change(rt[x],1,M,z,1);
		change(rt[y],1,M,z,1);
		change(rt[lca],1,M,z,-1);
		change(rt[f[lca][0]],1,M,z,-1);
	}
	
	dfs(1,0);
	
	for(int i=1; i<=n; i++)
		printf("%d\n",ans[i]);
			
	return 0;
}

Lomsat gelral

（题目传送门）

题目大意

  • 有一棵 \(n\) 个结点的以 \(1\) 号结点为根的有根树。

  • 每个结点都有一个颜色，颜色是以编号表示的， \(i\) 号结点的颜色编号为 \(c_i\)。

  • 如果一种颜色在以 \(x\) 为根的子树内出现次数最多，称其在以 \(x\) 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。

  • 你的任务是对于每一个 \(i\in[1,n]\)，求出以 \(i\) 为根的子树中，占主导地位的颜色的编号和。

解题思路

  • 对每个节点建立一棵权值线段树，维护占主导地位的颜色的出现次数和编号和，再进行一次 \(\mathrm{dfs}\) 合并线段树即可

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=100010,M=100000;

struct SegmentTree
{
	int lc,rc;
	LL dat,sum;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define dat(x)  tree[x].dat
	#define sum(x)  tree[x].sum
}tree[20*N];

int n,c[N],rt[N],tot;
LL ans[N];
vector <int> g[N];

void pushup(int p)
{
	if(dat(lc(p))==dat(rc(p)))
		sum(p)=sum(lc(p))+sum(rc(p)),dat(p)=dat(lc(p));
	else if(dat(lc(p))>dat(rc(p)))
		sum(p)=sum(lc(p)),dat(p)=dat(lc(p));
	else
		sum(p)=sum(rc(p)),dat(p)=dat(rc(p));
}

void change(int &p,int l,int r,int pos,int v)
{
	if(!p)
		p=++tot;
		
	if(l==r)
	{
		dat(p)+=(LL)v;
		sum(p)=pos;
		return; 
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v);
	else
		change(rc(p),mid+1,r,pos,v); 
		
	pushup(p);
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
	
	if(l==r)
	{
		dat(p)+=dat(q);
		sum(p)=l;
		return p;
	}
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	pushup(p);
	
	return p;
}

void dfs(int x,int fa)
{
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		if(y==fa)
			continue;
		
		dfs(y,x);
		
		rt[x]=merge(rt[x],rt[y],1,M);
	}
	
	ans[x]=sum(rt[x]);
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d",&c[i]);
		change(rt[i],1,M,c[i],1);
	}
	for(int i=1; i<n; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	} 
	
	dfs(1,0);

	for(int i=1; i<=n; i++)
		printf("%lld ",ans[i]);
	
	return 0;
}

[HNOI2012] 永无乡

（题目传送门）

题目大意

永无乡包含 \(n\) 座岛，编号从 \(1\) 到 \(n\) ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 \(n\) 座岛排名，名次用 \(1\) 到 \(n\) 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 \(a\) 出发经过若干座（含 \(0\) 座）桥可以 到达岛 \(b\) ，则称岛 \(a\) 和岛 \(b\) 是连通的。

现在有两种操作：

  • B x y 表示在岛 \(x\) 与岛 \(y\) 之间修建一座新桥。

  • Q x k 表示询问当前与岛 \(x\) 连通的所有岛中第 \(k\) 重要的是哪座岛，即所有与岛 \(x\) 连通的岛中重要度排名第 \(k\) 小的岛是哪座，请你输出那个岛的编号。

对于每个询问操作都要依次输出一行一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出 \(-1\) 。

解题思路

  • 考虑用并查集去维护每座岛之间的连通性，并用连通块的祖先去代表整个连通块

  • 对每座岛建立一棵权值线段树，每次查询操作在线段树上二分即可

  • 对于建桥操作，合并两个连通块即可

代码

#include<bits/stdc++.h>
using namespace std;

const int N=100010,M=100000;

struct SegmentTree
{
	int lc,rc;
	int sum,id;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define sum(x)  tree[x].sum
	#define id(x)  tree[x].id
}tree[20*N];

int n,m,q,rk[N];
int fa[N],rt[N],tot;

int get(int x)
{
	if(x==fa[x])
		return x;
	return fa[x]=get(fa[x]);
}

void change(int &p,int l,int r,int pos,int v,int idd)
{
	if(!p)
		p=++tot;
		
	if(l==r)
	{
		sum(p)+=v;
		id(p)=idd;
		return;
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v,idd);
	else
		change(rc(p),mid+1,r,pos,v,idd); 
		
	sum(p)=sum(lc(p))+sum(rc(p));
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
	
	if(l==r)
	{
		sum(p)+=sum(q);
		id(p)=id(q);
		return p;
	}
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	sum(p)=sum(lc(p))+sum(rc(p));
	
	return p;
}

int ask(int p,int l,int r,int k)
{
	if(l==r)
		return id(p);
		
	if(sum(p)<k)
		return -1;
	
	int mid=(l+r)>>1;
	if(sum(lc(p))>=k)
		return ask(lc(p),l,mid,k);
	return ask(rc(p),mid+1,r,k-sum(lc(p)));
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
	{
		scanf("%d",&rk[i]);
		change(rt[i],1,M,rk[i],1,i);
	}
	
	for(int i=1; i<=n; i++)
		fa[i]=i;
	
	for(int i=1; i<=m; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		
		int fx=get(x),fy=get(y);
		if(fx==fy)
			continue;
			
		int rtt=merge(rt[fy],rt[fx],1,M);
		rt[fy]=rtt;
		fa[fx]=fy;
	}
	
	scanf("%d",&q);
	while(q--)
	{
		char op[2];
		int x,y,k;
		
		scanf("%s",op);
		if(op[0]=='B')
		{
			scanf("%d%d",&x,&y);
			
			int fx=get(x),fy=get(y);
			if(fx==fy)
				continue;
				
			int rtt=merge(rt[fy],rt[fx],1,M);	
			rt[fy]=rtt;
			fa[fx]=fy;
		}
		else
		{
			scanf("%d%d",&x,&k);
			printf("%d\n",ask(rt[get(x)],1,M,k));
		}
	}
	
	return 0;
}

[POI2011] ROT-Tree Rotations

（题目传送门）

题目大意

给定一颗有 \(n\) 个叶节点的二叉树。每个叶节点都有一个权值 \(p_i\)（注意，根不是叶节点），所有叶节点的权值构成了一个 \(1 \sim n\) 的排列。

对于这棵二叉树的任何一个结点，保证其要么是叶节点，要么左右两个孩子都存在。

现在你可以任选一些节点，交换这些节点的左右子树。

在最终的树上，按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 \(n\) 的排列，你需要最小化这个排列的逆序对数。

非常毒瘤的输入格式

第一行是一个整数 \(n\)，表示树的叶节点个数。
接下来若干行，使用递归的形式来读入这棵树，读入任意一个子树的信息时，初始时读入其根节点。对于一个结点 \(u\)，首先有一行一个整数 \(x\)。

  • 若 \(x \neq 0\)，则表示 \(u\) 是一个叶节点，其权值为 \(x\)。

  • 若 \(x = 0\)，则表示 \(u\) 不是叶节点，则接下来若干行读入其左子树信息，左子树读入结束后接下来若干行读入其右子树信息。

解题思路

  • 对于节点 \(x\)，设它的儿子子树分别为 \(y_1,y_2\)，并且 \(y_1\) 在 \(y_2\) 左边。分析逆序对的来源：

    1.在同一个 \(y\) 子树

    2.在不同的 \(y\) 子树

  • 对于节点 \(x\) 来说，要做的就是合并 \(y_1,y_2\) 并计算贡献。显然第 \(1\) 种来源已经在以 \(y_1,y_2\) 为根的子树中计算过了，所以我们只需通过合并操作计算来源 \(2\)

  • 考虑对每个节点建立权值线段树，设值域区间内数字的个数为 \(sum\),那么逆序对个数就是 \(sum(rc(p))*sum(lc(q))\)

  • 现在考虑交换子树的操作。显然交换子树的操作只会对来源2产生影响。那我们取 \(sum(lc(p))*sum(rc(q))\) 和 \(sum(rc(p))*sum(lc(q))\) 的最小值即可

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=200010;

struct SegmentTree
{
	int lc,rc;
	LL sum;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define sum(x)  tree[x].sum
}tree[20*N];

int n,rt[N*20],tot,cnt;
LL ans,ansa,ansb;

void change(int &p,int l,int r,int pos,int v)
{
	if(!p)
		p=++tot;
		
	if(l==r)
	{
		sum(p)+=(LL)v;
		return; 
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v);
	else
		change(rc(p),mid+1,r,pos,v); 
		
	sum(p)=sum(lc(p))+sum(rc(p));
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
	
	if(l==r)
	{
		sum(p)+=sum(q);
		return p;
	}
	
	ansa+=sum(lc(p))*sum(rc(q));
	ansb+=sum(rc(p))*sum(lc(q));
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	sum(p)=sum(lc(p))+sum(rc(p));
	
	return p;
}

int dfs()
{
	int x;
	scanf("%d",&x);
	
	++cnt;
	if(x==0)
	{
		int lx=dfs(),rx=dfs();
		ansa=ansb=0;
		rt[cnt]=merge(lx,rx,1,n);
		ans+=min(ansa,ansb);
	}
	else
		change(rt[cnt],1,n,x,1);
	
	return rt[cnt];
}

int main()
{
	scanf("%d",&n);
	
	dfs();
	
	printf("%lld",ans);
	
	return 0;
}

Blood Cousins

（题目传送门）

题目大意

有一个家族关系树，描述了 \(n\)（\(1\leq n\leq 10 ^ 5\)）人的家庭关系，成员编号为 \(1\) 到 \(n\) 。

如果 \(a\) 是 \(b\) 的父亲，那么称 \(a\) 为 \(b\) 的 \(1\) 级祖先；如果 \(b\) 有一个 \(1\) 级祖先，\(a\) 是 \(b\) 的 \(1\) 级祖先的 \(k-1\) 级祖先，那么称 \(a\) 为 \(b\) 的 \(k\) 级祖先。

家庭关系保证是一棵树，树中的每个人都只有一个父母，且自己不会是自己的祖先。

如果存在一个人 \(z\) ，是两个人 \(a\) 和 \(b\) 共同的 \(p\) 级祖先：那么称 \(a\) 和 \(b\) 为 \(p\) 级表亲。

\(m\)（\(1\leq m\leq 10 ^ 5\)）次询问，每次询问给出一对整数 \(v\) 和 \(p\)，求编号为 \(v\) 的人有多少个 \(p\) 级表亲。

解题思路

  • 直接找 \(a\) 的 \(p\) 级表亲是比较困难的，所以考虑先求出 \(a\) 的 \(p\) 级祖先 \(z\)，将询问离线转化到 \(z\) 上，再求 \(z\) 子树内有多少个深度等于 \(dep[z]+p\) 的节点，记为 \(cnt\)，那么该询问的答案就是 \(cnt-1\)

  • 对于节点 \(x\)，考虑如何求出其子树内有多少个深度为 \(dep[x]+p\) 的节点。我们可以以深度为下标建立权值线段树，查询时单点查询，然后不断合并即可。

  • 具体实现时，在树的遍历时，可以开两个数组对询问进行处理。求 \(x\) 的 \(p\) 级祖先，可以树上倍增，也可以开一个栈，在遍历到节点 \(x\) 时入栈，返回时出栈，设当前栈顶下标为 \(t\)，这样显然 \(x\) 的 \(p\) 级祖先就是 \(s[t-p]\)

  • 一个小细节，该题的图不一定只有一课树，可能是多棵树，需要注意。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1000010,M=1000000;

struct SegmentTree
{
	int lc,rc;
	int sum;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define sum(x)  tree[x].sum
}tree[8*N];

int n,q,rt[N],tot,ans[N];
int father[N],dep[N],size[N],s[N],t;
vector <int> g[N];
vector < pair<int,int> > qa[N],qb[N];

void pushup(int p)
{
	sum(p)=sum(lc(p))+sum(rc(p));
}

void change(int &p,int l,int r,int pos,int v)
{
	if(!p)
		p=++tot;
		
	if(l==r)
	{
		sum(p)+=v;
		return; 
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v);
	else
		change(rc(p),mid+1,r,pos,v); 
		
	pushup(p);
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
	
	if(l==r)
	{
		sum(p)+=sum(q);
		return p;
	}
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	pushup(p);
	
	return p;
}

int ask(int p,int l,int r,int pos)
{
	if(l==r)
		return sum(p);
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		return ask(lc(p),l,mid,pos);
	return ask(rc(p),mid+1,r,pos);
}

void solve(int x)
{
	s[++t]=x; //入栈
	for(int i=0; i<qa[x].size(); i++) //转化问题
	{
		int k=qa[x][i].first,id=qa[x][i].second;
		if(t>k)
			qb[s[t-k]].push_back(make_pair(dep[x],id));
	}
	
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		
		solve(y);
		rt[x]=merge(rt[x],rt[y],1,M);
	}
	
	change(rt[x],1,M,dep[x],1);
	
	for(int i=0; i<qb[x].size(); i++) //求解问题
	{
		int k=qb[x][i].first,id=qb[x][i].second;
		ans[id]=ask(rt[x],1,M,k);
	}
	
	t--; //出栈
}

void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	size[x]=1;
	
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		
		dfs(y,x);
		size[x]+=size[y];
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		int x;
		scanf("%d",&x);
		g[x].push_back(i);
		father[i]=x;
	}
	
	for(int i=1; i<=n; i++)
		if(father[i]==0)	
			dfs(i,0);
	
	scanf("%d",&q);
	for(int i=1; i<=q; i++)
	{
		int x,k;
		scanf("%d%d",&x,&k);
		qa[x].push_back(make_pair(k,i));
	}
	
	for(int i=1; i<=n; i++)
		if(father[i]==0)	
			solve(i);
	
	for(int i=1; i<=q; i++)
		printf("%d ",max(ans[i]-1,0));
	
	return 0;
}

[Cnoi2019] 雪松果树

（题目传送门）

题目大意

（上一题 Blood Cousins 的卡空间版）

雪松果树是一个以 \(1\) 为根有着 \(N\) 个节点的树。

\(Q\) 个询问，每个询问是一个二元组 \((u,k)\) ,表示询问 \(u\) 节点的 \(k\)-cousin 有多少个。

解题思路

  • 大部分代码和上一题相同，这里主要讲如何优化空间

  • 首先合并时，将子树按 \(size\) 从大到小合并，这样可以减少合并时的空间浪费

  • 其次，合并完后，将无用的那个子树的空间回收起来，以后在动态开店时，优先从回收站里拿空间

  • 最后，把 vector 换成链式前向星

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1000010,M=1000000;

struct SegmentTree
{
	int lc,rc;
	int sum;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define sum(x)  tree[x].sum
}tree[8*N];

struct node
{
	int k,id,nxtt;
}qa[N],qb[N]; //qa,qb与上一题相同
int n,q,rt[N],tot,ans[N];
int dep[N],size[N],a[N],cnt;
int ha[N],tota,hb[N],totb;
int sa[N],ta,sb[N],tb; //sa是求k-祖先的栈,sb是回收空间用的
vector <int> g[N];

void adda(int x,int k,int id)
{
	qa[++tota]=(node){k,id,ha[x]};
	ha[x]=tota;
}

void addb(int x,int k,int id)
{
	qb[++totb]=(node){k,id,hb[x]};
	hb[x]=totb;
}

bool cmp(int x,int y)
{
	return size[x]>size[y];
}

void pushup(int p)
{
	sum(p)=sum(lc(p))+sum(rc(p));
}

void change(int &p,int l,int r,int pos,int v)
{
	if(!p)
	{
		if(tb)
			p=sb[tb--]; //优先拿回收站
		else
			p=++tot;
	}
		
	if(l==r)
	{
		sum(p)+=v;
		return; 
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v);
	else
		change(rc(p),mid+1,r,pos,v); 
		
	pushup(p);
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
	
	if(l==r)
	{
		sum(p)+=sum(q);
		lc(q)=rc(q)=sum(q)=0; //回收
		sb[++tb]=q;
		return p;
	}
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	pushup(p);
	
	lc(q)=rc(q)=sum(q)=0;
	sb[++tb]=q;
	
	return p;
}

int ask(int p,int l,int r,int pos)
{
	if(l==r)
		return sum(p);
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		return ask(lc(p),l,mid,pos);
	return ask(rc(p),mid+1,r,pos);
}

void solve(int x)
{
	sa[++ta]=x;
	for(int i=ha[x]; i; i=qa[i].nxtt)
	{
		int k=qa[i].k,id=qa[i].id;
		if(ta>k)
			addb(sa[ta-k],dep[x],id);
	}
	
	int l=cnt;
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		a[++cnt]=y;
	}
	int r=cnt;
	
	sort(a+l+1,a+r+1,cmp); //按子树大小从大到小排序
	
	for(int i=l+1; i<=r; i++)
	{
		int y=a[i];
		
		solve(y);
		rt[x]=merge(rt[x],rt[y],1,M);
	}
	
	change(rt[x],1,M,dep[x],1);
	
	for(int i=hb[x]; i; i=qb[i].nxtt)
	{
		int k=qb[i].k,id=qb[i].id;
		ans[id]=ask(rt[x],1,M,k);
	}
	
	ta--;
}

void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	size[x]=1;
	
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		
		dfs(y,x);
		size[x]+=size[y];
	}
}

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=2; i<=n; i++)
	{
		int x;
		scanf("%d",&x);
		g[x].push_back(i);
	}
	
	dfs(1,0);
	
	for(int i=1; i<=q; i++)
	{
		int x,k;
		scanf("%d%d",&x,&k);
		adda(x,k,i);
	}
	
	solve(1);
	
	for(int i=1; i<=q; i++)
		printf("%d ",max(ans[i]-1,0));
	
	return 0;
}

[湖南集训] 更为厉害

（题目传送门）

题目大意

设 \(\text T\) 为一棵有根树，我们做如下的定义：

  • 设 \(a\) 和 \(b\) 为 \(\text T\) 中的两个不同节点。如果 \(a\) 是 \(b\) 的祖先，那么称“\(a\) 比 \(b\) 更为厉害”。
  • 设 \(a\) 和 \(b\) 为 \(\text T\) 中的两个不同节点。如果 \(a\) 与 \(b\) 在树上的距离不超过某个给定常数 \(x\)，那么称“ \(a\) 与 \(b\) 彼此彼此”。

给定一棵 \(n\) 个节点的有根树 \(\text T\)，节点的编号为 \(1\) 到 \(n\)，根节点为 \(1\) 号节点。
你需要回答 \(q\) 个询问，询问给定两个整数 \(p\) 和 \(k\)，问有多少个有序三元组 \((a,b,c)\) 满足：

  1. \(a,b,c\) 为 \(\text T\) 中三个不同的点，且 \(a\) 为 \(p\) 号节点；
  2. \(a\) 和 \(b\) 都比 \(c\) 更为厉害；
  3. \(a\) 和 \(b\) 彼此彼此。这里彼此彼此中的常数为给定的 \(k\)。

解题思路

  • 因为 \(a,b\) 都是 \(c\) 的祖先，所以容易看出 \(a,b,c\) 在同一条链上

  • 如果 \(b\) 在 \(a\) 的上方，显然答案就是 \((size[a]-1)\times \min(dep[a]-1,k)\)

  • 如果 \(b\) 在 \(a\) 的下方，那么 \(a\) 子树内所有深度在 \([dep[a]+1,dep[a]+k]\) 范围内的点都可以作为 \(b\) 的候选项，此时 \(c\) 的数量就是 \(size[b]-1\)。因此我们可以以深度为下标建立权值线段树，求下标为 \([dep[a]+1,dep[a]+k]\) 内的 \(size-1\) 的和即可

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=300010;

struct SegmentTree
{
	int lc,rc;
	LL sum;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define sum(x)  tree[x].sum
}tree[20*N];

int n,q,rt[N],tot,dep[N],size[N];
LL ans[N];
vector <int> g[N];
vector < pair<int,int> > qq[N];

void change(int &p,int l,int r,int pos,int v)
{
	if(!p)
		p=++tot;
		
	if(l==r)
	{
		sum(p)+=(LL)v;
		return; 
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v);
	else
		change(rc(p),mid+1,r,pos,v);
	
	sum(p)=sum(lc(p))+sum(rc(p));
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
		
	if(l==r)
	{
		sum(p)+=sum(q);
		return p;
	}
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	sum(p)=sum(lc(p))+sum(rc(p));
	
	return p;
}

LL ask(int p,int l,int r,int ql,int qr)
{
	if(!p)
		return 0;
		
	if(ql<=l && qr>=r)
		return sum(p);
	
	int mid=(l+r)>>1;
	LL val=0;
	if(ql<=mid)
		val+=ask(lc(p),l,mid,ql,qr);
	if(qr>mid)
		val+=ask(rc(p),mid+1,r,ql,qr);
	
	return val; 
}

void dfs1(int x,int fa)
{
	dep[x]=dep[fa]+1;
	size[x]=1;
	
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		if(y==fa)
			continue;
			
		dfs1(y,x);
		
		rt[x]=merge(rt[x],rt[y],1,n);
		size[x]+=size[y];
	}
	
	change(rt[x],1,n,dep[x],size[x]-1);
	
	for(int i=0; i<qq[x].size(); i++)
	{
		int id=qq[x][i].first,k=qq[x][i].second;
		ans[id]=ask(rt[x],1,n,min(n,dep[x]+1),min(n,dep[x]+k))+1LL*(size[x]-1)*min(dep[x]-1,k);
	}
}

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1; i<n; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	for(int i=1; i<=q; i++)
	{
		int x,k;
		scanf("%d%d",&x,&k);
		qq[x].push_back(make_pair(i,k));
	}
	
	dfs1(1,0);
	
	for(int i=1; i<=q; i++)
		printf("%lld\n",ans[i]);
	
	return 0;
}

Tree Requests

（题目传送门）

题目大意

给定一个以 \(1\) 为根的 \(n\) 个结点的树，每个点上有一个字母（a-z），每个点的深度定义为该节点到 \(1\) 号结点路径上的点数。每次询问 \(a, b\) 查询以 \(a\) 为根的子树内深度为 \(b\) 的结点上的字母重新排列之后是否能构成回文串。

解题思路

  • 在每个节点同样以深度为下标建立线段树，存储该子树内深度相同的点所构成的字符集合

  • 因为题目要求的是能否构成回文串。显然只要所有的字符都出现偶数次或只有一个字符出现次数为 \(1\) 即可，那么考虑将 \(26\) 个字母二进制压缩，每次 check 一下这个二进制数是否合法即可

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=500010;

struct SegmentTree
{
	int lc,rc;
	int dat;
	bool flag;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define dat(x)  tree[x].dat
	#define flag(x)  tree[x].flag
}tree[20*N];

int n,m,a[N],rt[N],tot,dep[N];
bool ans[N];
char s[N]; 
vector <int> g[N];
vector < pair<int,int> > qq[N];

bool check(int sta)
{
	if(sta&-sta)
	{
		sta-=(sta&-sta);
		if(sta&-sta)
			return 0;
		return 1;
	}
	return 1;
}

void change(int &p,int l,int r,int pos,int v)
{
	if(!p)
		p=++tot;
		
	if(l==r)
	{
		dat(p)^=(1<<v);
		flag(p)=check(dat(p));
		return; 
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v);
	else
		change(rc(p),mid+1,r,pos,v);
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
		
	if(l==r)
	{
		dat(p)^=dat(q);
		flag(p)=check(dat(p));
		return p;
	}
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	
	return p;
}

bool ask(int p,int l,int r,int pos)
{
	if(!p)
		return 1;
	if(l==r)
		return flag(p);
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		return ask(lc(p),l,mid,pos);
	return ask(rc(p),mid+1,r,pos);
}

void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
			
		dfs(y,x);
		
		rt[x]=merge(rt[x],rt[y],1,n);
	}
	
	change(rt[x],1,n,dep[x],a[x]);
	
	for(int i=0; i<qq[x].size(); i++)
	{
		int id=qq[x][i].first,k=qq[x][i].second;
		ans[id]=ask(rt[x],1,n,k);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=2; i<=n; i++)
	{
		int x;
		scanf("%d",&x);
		g[x].push_back(i);
	}
	
	scanf("%s",s+1);
	for(int i=1; i<=n; i++)
		a[i]=int(s[i]-'a');
	
	for(int i=1; i<=m; i++)
	{
		int x,k;
		scanf("%d%d",&x,&k);
		qq[x].push_back(make_pair(i,k));
	}
	
	dfs(1,0);
	
	for(int i=1; i<=m; i++)
	{
		if(ans[i])
			printf("Yes\n");
		else
			printf("No\n");
	}
	
	return 0;
}

Blood Cousins Return

（题目传送门）

题目大意

给定一片森林，每次询问一个节点的 K-Son 共有个多少不同的名字。一个节点的 K-Son 即为在该节点子树内的，深度是该节点深度加 \(K\) 的节点。

解题思路

  • 容易想到用 map 给每个名字编号

  • 对每个节点同样以深度为下标建立权值线段树，因为要去重计数，所以对线段树的每个叶子节点开一个 set，查询时返回 set 的大小即可

  • 合并时，同 \(\text{雪松果树}\)，将小的 set 合并到大的上

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=100010;

struct SegmentTree
{
	int lc,rc;
	set <int> s;
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define s(x)  tree[x].s
}tree[20*N];

int n,m,tot,rt[N],a[N];
int father[N],dep[N],ans[N],cnt;
string str[N];
map <string,int> name; 
vector <int> g[N];
vector < pair<int,int> > qq[N];

int Set_merge(int p,int q)
{
	if(s(p).size()>s(q).size())
	{
		set <int> ::iterator it;
		for(it=s(q).begin(); it!=s(q).end(); it++)
			s(p).insert(*it);
		return p;
	}
	else
	{
		set <int> ::iterator it;
		for(it=s(p).begin(); it!=s(p).end(); it++)
			s(q).insert(*it);
		return q;
	}
}

void change(int &p,int l,int r,int pos,int v)
{
	if(!p)
		p=++tot;
		
	if(l==r)
	{
		s(p).insert(v);
		return; 
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		change(lc(p),l,mid,pos,v);
	else
		change(rc(p),mid+1,r,pos,v);
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
		
	if(l==r)
		return Set_merge(p,q);
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	
	return p;
}

int ask(int p,int l,int r,int pos)
{
	if(!p || pos>r)
		return 0;
	if(l==r)
		return s(p).size();
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		return ask(lc(p),l,mid,pos);
	return ask(rc(p),mid+1,r,pos);
}

void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
			
		dfs(y,x);
		
		rt[x]=merge(rt[x],rt[y],1,n);
	}
	
	change(rt[x],1,n,dep[x],a[x]);
	
	for(int i=0; i<qq[x].size(); i++)
	{
		int id=qq[x][i].first,k=qq[x][i].second;
		ans[id]=ask(rt[x],1,n,dep[x]+k);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		cin>>str[i];
		scanf("%d",&father[i]);
		
		g[father[i]].push_back(i);
		if(name.find(str[i])==name.end())
		{
			name[str[i]]=++cnt;
			a[i]=cnt;
		}
		else
			a[i]=name[str[i]];
	}
	
	scanf("%d",&m);
	for(int i=1; i<=m; i++)
	{
		int x,k;
		scanf("%d%d",&x,&k);
		qq[x].push_back(make_pair(i,k));
	}
	
	for(int i=1; i<=n; i++)
		if(!father[i])
			dfs(i,0);
	
	for(int i=1; i<=m; i++)
		printf("%d\n",ans[i]);
	
	return 0;
}

Escape Through Leaf

（题目传送门）

题目大意

有一颗 \(n\) 个节点的树（节点从 \(1\) 到 \(n\) 依次编号），根节点为 \(1\)。每个节点有两个权值，第 \(i\) 个节点的权值为 \(a_i,b_i\)。

你可以从一个节点跳到它的子树内任意一个节点上。从节点 \(x\) 跳到节点 \(y\) 一次的花费为 \(a_x\times b_y\)。跳跃多次走过一条路径的总费用为每次跳跃的费用之和。请分别计算出每个节点到达树的每个叶子节点的费用中的最小值。

注意：就算根节点的度数为 \(1\)，根节点也不算做叶子节点。另外，不能从一个节点跳到它自己.

解题思路

  • （李超线段树的合并）

  • 考虑树形 \(\mathrm{dp}\)，设 \(x\) 的儿子为 \(y\)，\(f[x]\) 表示 \(x\) 跳到叶子节点费用的最小值。则显然

    \[f[x]=\min\{f[y]+a_x\times b_y\} \]

  • 把 \(b_y\) 当作斜率，\(f[y]\) 当作截距，则变成李超线段树的模板，求平面内所有直线与直线 \(x=a_x\) 的交点的纵坐标最小值是多少

  • 在合并时，对于表示相同区间的节点 \(p,q\)（\(p,q\) 非空），要做的就是把在 \(p\) 这里插入一条 \(tree[q]\) 的直线即可

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=100010,M=100000;
const LL INF=1e16;

struct line
{
	LL k,b;
	int lc,rc;
	bool flag;
	#define k(x)  tree[x].k
	#define b(x)  tree[x].b
	#define lc(x)  tree[x].lc
	#define rc(x)  tree[x].rc
	#define flag(x)  tree[x].flag
}tree[20*N];

int n,a[N],b[N];
int rt[N],tot;
LL f[N];
vector <int> g[N];

LL calc(line a,int x)
{
	return 1LL*a.k*x+a.b;
}

void change(int &p,int l,int r,line k)
{
	if(!p)
		p=++tot;
		
	if(!flag(p))
		k(p)=k.k,b(p)=k.b,flag(p)=1;	
	else if(calc(k,l)<calc(tree[p],l) && calc(k,r)<calc(tree[p],r))
		k(p)=k.k,b(p)=k.b;
	else if(calc(k,l)<calc(tree[p],l) || calc(k,r)<calc(tree[p],r))
	{
		int mid=(l+r)>>1;
		
		if(calc(k,mid)<calc(tree[p],mid))
			swap(k(p),k.k),swap(b(p),k.b);
		if(calc(k,l)<calc(tree[p],l))
			change(lc(p),l,mid,k);
		else
			change(rc(p),mid+1,r,k);
	}
}

int merge(int p,int q,int l,int r)
{
	if(!p)
		return q;
	if(!q)
		return p;
	
	change(p,l,r,tree[q]);
	if(l==r)
		return p;
	
	int mid=(l+r)>>1;
	lc(p)=merge(lc(p),lc(q),l,mid);
	rc(p)=merge(rc(p),rc(q),mid+1,r);
	
	return p;
}

LL ask(int p,int l,int r,int x)
{
	if(!p)
		return INF;
	if(l==r)
	{
		if(flag(p))
			return calc(tree[p],x);
		return INF;
	}
	
	int mid=(l+r)>>1;
	LL val=INF;
	if(flag(p))
		val=calc(tree[p],x);
	if(x<=mid)
		return min(val,ask(lc(p),l,mid,x));
	return min(val,ask(rc(p),mid+1,r,x)); 
}

void dfs(int x,int fa)
{
	for(int i=0; i<g[x].size(); i++)
	{
		int y=g[x][i];
		if(y==fa)
			continue;
		
		dfs(y,x);
		
		rt[x]=merge(rt[x],rt[y],-M,M);
	}
	
	f[x]=ask(rt[x],-M,M,a[x]);
	if(f[x]==INF)
		f[x]=0;
	
	line now={(LL)b[x],f[x],0,0,1};
	change(rt[x],-M,M,now);
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for(int i=1; i<=n; i++)
		scanf("%d",&b[i]);
	for(int i=1; i<n; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(1,0);
	
	for(int i=1; i<=n; i++)
		printf("%lld ",f[i]);
	
	return 0;
}