图论好题推荐-逛公园

题目

题解

前置知识

学会使用 tarjan 算法找环，会使用树上倍增求两点间路径的编号最大值与最小值。

思路

设 $p_i$ 为 $i$ 作为题目中的 $l$ ，可以匹配到的最大 $r$ 。因为 $r$ 越大，包含的边和点就越多，所以 $[i,i],[i,i+1],[i,p_i-1],[i,p_i]$ 作为 $[l,r]$ 都是可以满足题意的。
下面考虑两个问题：

1. 如何求 $p_i$？
2. 如何利用 $p_i$ 求解答案？

如何求 $p_{i} $？

首先找环,可以遍历一棵 DFS 搜索树，如果出现返租边，就是出现了环。
对于每个环，求出环中点的编号的最大值（记为 $max1$）与最小值（记为 $min1$）。因为每次出现环是在出现返祖边的时候，所以求一下这条返祖边所连接的两个点之间路径上的点中的编号的最大值和最小值即可，可以用倍增优化，$log$ 级别。显然，如果某个区间 $[l,r]$ 同时包含这个环的 $min1$ 与 $max1$,则该区间 $[l,r]$ 一定不合法,反之，该区间 $[l,r]$ 不会在这个环中不合法。
记 $pos_{i} $ 为 $i$ 作为环中编号最小点时，其对应的环中的编号最大点的编号最小值。因为同一个点有可能存在于多个环中（如图一），并且有可能在这些环中都是编号最小的点，所以要取对应的编号最大点的编号最小值。
这里的用处以后会知道。

图一。题目中只保证不存在一条边同时存在于两个不同的简单环，但可能有一个点在多个环中。

每次找到环时，$po{s}_{min1}=min(po{s}_{min1},max1)$ 更新即可。
求 $p_i$，考虑 $j(i\le j\le n)$,$j$ 带给 $p_{i} $ 的限制就是：$p_{i} < pos_{j} $，因为如果 $p_{i} $ 取到 $po{s}_j$ 或者更大，就会同时包含 $j$ 和 $po{s}_j$，不合法。那么显然 $p_i=\min (po{s}_j-1)$，求一个后缀最小值即可。

图二。结合样例理解 $pos$ 数组和 $p$ 数组含义（INF表示没有）。

编号	1	2	3	4	5	6	7	8
pos	3	INF	INF	8	INF	INF	INF	INF
p	2	7	7	7	8	8	8	8

如何利用 $p_i$ 求解答案？

可以暴力枚举 $j$ 从 $x$ 到 $y$，答案即为 ${\sum }_{j=x}^y(min(y,p_j)-j+1)$，时间复杂度$O(nq)$ 。
考虑优化，显然可以看出，$p$ 数组是单调不降的，故可以二分出在 $x$ 与 $y$ 之间第一个$p[]\ge y$ 的点，下标记为 $k$。对于任意 $j(k\le j\le )$，有 $y\le p_j$，故 $min(y,p_j)=y$,其贡献为 ${\sum }_{j=k}^y(y-j+1)$，整理得 ${\sum }_{j=k}^y(-j+1)+{\sum }_{j=k}^{y}y$，可$O(1)$求出。
对于任意 KaTeX parse error: Undefined control sequence: \lej at position 4: j(x\̲l̲e̲j̲＜k)，有 $min(y,p_j)=p_j$。故其贡献为 ${\sum }_{j=x}^{k-1}(p_j-j+1)$，整理得 ${\sum }_{j=x}^{k-1}{p}_j+{\sum }_{j=x}^{k-1}(-j+1)$，预处理前缀和，也可 $O(1)$ 求出。
求解答案的总复杂度为 $O(q{\log }_{2}n)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=3e5+5;
bool_priority birdtjg=1;
int n,m,q;
vector<int> a[N];
int p[N],dfn[N],fmin_[N][30],fmax_[N][30],to[N][30],pos[N];
long long sp[N];      //注意开long long!
void dfs(int x,int fa)
{
	dfn[x]=dfn[fa]+1;  //dfn为深度
	fmin_[x][0]=min(fa,x),fmax_[x][0]=max(fa,x);
	to[x][0]=fa;
	for(int i=1;i<=20;i++) //倍增优化
	{
		to[x][i]=to[to[x][i-1]][i-1];
		fmin_[x][i]=min(fmin_[x][i-1],fmin_[to[x][i-1]][i-1]);
		fmax_[x][i]=max(fmax_[x][i-1],fmax_[to[x][i-1]][i-1]);
	}
	for(int i=0;i<a[x].size();i++)
	{
		if(!dfn[a[x][i]])
			dfs(a[x][i],x);
		else if(dfn[a[x][i]]<dfn[x]&&a[x][i]!=fa) //出现返祖边(注意特判父亲!)
		{
			int min1=1e9,max1=0,now=x;
			for(int j=20;j>=0;j--) //倍增求min1和max1
			{
				if(dfn[to[now][j]]>=dfn[a[x][i]])
				{
					min1=min(min1,fmin_[now][j]);
					max1=max(max1,fmax_[now][j]);
					now=to[now][j];
				}
			}
			pos[min1]=min(pos[min1],max1);  //求pos[]
		}
	}
}
int main()
{
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	memset(pos,127,sizeof(pos));  //因为要取min,所以要赋值为INF
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		a[u].push_back(v);   
		a[v].push_back(u);
	}
	dfs(1,0);    //预处理
	int hmin=1e9;       
	for(int i=n;i>=1;i--) //从n到1遍历方便求后缀最小值
	{
		hmin=min(hmin,pos[i]-1);//因为pos[i]肯定是小于等于n的,如果不是,就意味着该点没有出现在某个环的min1
		if(hmin>n) p[i]=n;     //如果后缀最小值大于n,说明没有限制,赋值为n
		else p[i]=hmin;
	}
	for(int i=1;i<=n;i++)  //前缀和
		sp[i]=sp[i-1]+p[i];
	scanf("%d",&q);
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);	
		int l=x,r=y,k=0;   //肯定能够二分出至少一个p[j]>=y
		long long ans=0;  //注意开long long!
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(p[mid]>=y) k=mid,r=mid-1;
			else l=mid+1;
		}
		ans=1ll*(y-k+2)*(y-k+1)/2;  //求>=k的贡献
		ans+=sp[k-1]-sp[x-1]-1ll*(k-x)*(x+k-3)/2; //求<k的贡献
		//求解的过程中可能爆int,注意用1ll*
		printf("%lld\n",ans);
	}
	return 0;
}

小细节

• 前缀和数组和答案都需要开long long。求解的过程中也有可能爆 int,注意用1ll*（详见注释）。
• 题目中说不存在一条边同时存在于两个不同的简单环，所以求环中点的 $min1$ 和 $max1$ 的时候，直接暴力枚举整个环即可，每条边最多被遍历一次，$O(m)$ 复杂度下即可求解。 我贴的代码是倍增的，时间复杂度反而更大了。