JZOJ-senior-5919. 【NOIP2018模拟10.21】逛公园

程序员文章站 2022-05-27 16:17:13

...

Time Limits: 1000 ms Memory Limits: 262144 KB

Description

琥珀色黄昏像糖在很美的远方，思念跟影子在傍晚一起被拉长……

小 B 带着 GF 去逛公园，公园一共有 n 个景点，标号为 1 . . . n。景点之间有 m 条路径相连。

小 B 想选择编号在一段区间 [l, r] 内的景点来游玩，但是如果这些景点的诱导子图形成了环，那么 GF 将会不高兴。

小 B 给出很多个询问 [x, y]，想让你求有多少个区间 [l, r] 满足 x ≤ l, r ≤ y 且不会使 GF不高兴。

Input

第一行为两个整数 n, m，表示景点和路径的数量。
第 2 . . . m + 1 行每行两个整数 ui, vi 表示第 i 路径的两端。
第 m + 2 行是一个整数 q 表示询问的个数，接下来 m 行每行两个整数 xi, yi 表示询问。

Output

q 行，每行一个整数表示答案。

Sample Input

8 9
1 2
2 3
3 1
4 5
5 6
6 7
7 8
8 4
7 2
3
1 8
1 4
3 8

Sample Output

27
8
19

Data Constraint

对于 30% 的数据，n, m ≤ 100。
对于另外 10% 的数据，n = m + 1。
对于另外 10% 的数据，n = m
对于 100% 的数据，n, m ≤ 3 × 10^5, xi ≤ yi，不存在重边、自环，不存在一条边同时存在于两个不同的简单环。

Hint

诱导子图：子图 G′ = (V′, E′)，原图 G = (V, E)。V′ 是 V 的子集，E′ = {(u, v)|u, v ∈V′,(u, v) ∈ E}

Solution

题目意思就是求出不包含环的区间的个数
显然对于每个点开始往右最远可达的位置是递增的
我们在找环的时候就处理好每个点往右最远可达的不包含环的位置，记为 $R[i]$
为方便求答案，处理出前缀和数组 $S[i]$
对于每个询问 $l,r$ ，我们将 $R[i]<=r$ 的前缀和求，后面的等差数列求和即可

Code

#include<algorithm>
#include<cstdio>

#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long

using namespace std;

const int N=3e5+5;
int n,m,q,num,cnt,time;
int R[N],z[N],dfn[N],low[N],last[N];
ll S[N];
struct edge{int to,next;}e[2*N];

void link(int x,int y)
{
	e[++num]=(edge){y,last[x]},last[x]=num;
}

void Tarjan(int x,int fa)
{
	dfn[x]=low[x]=++time,z[++z[0]]=x;
	for(int w=last[x];w;w=e[w].next)
	{
		int y=e[w].to;
		if(y==fa) continue;
		if(!dfn[y])
		{
			Tarjan(y,x),low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y])
			{
				int mn=n+1,mx=0,gs=z[0];
				while(z[0])
				{
					int now=z[z[0]--];
					mn=min(mn,now);
					mx=max(mx,now);
					if(now==y) break;
				}
				mn=min(mn,z[z[0]]);
				mx=max(mx,z[z[0]]);
				if(gs-z[0]>1) R[mn]=min(R[mn],mx-1);
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}

int main()
{
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	scanf("%d%d",&n,&m);
	fo(i,1,m)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		link(x,y),link(y,x);
	}
	fo(i,1,n) R[i]=n;
	fo(i,1,n) if(!dfn[i]) Tarjan(1,0);
	fd(i,n-1,1) R[i]=min(R[i],R[i+1]);
	fo(i,1,n) S[i]=S[i-1]+R[i]-i+1;
	scanf("%d",&q);
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int pos=upper_bound(R+x,R+y,y)-R;
		ll ans=(ll)S[pos-1]-S[x-1]+(ll)(1+y-pos+1)*(ll)(y-pos+1)/2;
		printf("%lld\n",ans);
	}
}