Description：

给你一个 $n$ 个点 $m$ 条边且无偶环的图，现在有 $q$ 个询问。求区间 $[L,R]$ 中有多少个子区间 $[l,r]$ ，满足 $L\leqslant l \leqslant r \leqslant R$ ，并且一个只包含 $[l,r]$ 这些点的图为二分图。

$1\leqslant n\leqslant 3\times 10^5$

Solution：

首先没有偶环，那就是只有奇环，并且没有环套环，那么题目的限制实际上就是有多少个子区间中的点不含有环，那么我们可以用 $tarjan$ 把所有的环找出来，并求出环上最大点和环上最小点，显然包含这个区间的所有区间都是不合法的，设这个区间为 $[l_0,r_0]$ ，那么我们可以求出来一个 $f[i]$ 表示从 $i$ 开始的区间最长可以延伸到哪里，具体求法是每找到一个环就把 $f[l_0]=r_0$ ，然后再倒序循环，每个依次与它下一个取 $\min$ ，相当于做一个后缀和，那么答案就是 $\begin{align}\sum_{i=l}^r\min(f[i],r)-i+1\end{align}$ ，这样做时间复杂度是 $O(n^2)$ 的，但是我们发现由于 $f[i]$ 单调不降，所以可以二分出最大的 $f[i]\leqslant r$ 的位置然后用前缀和统计就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,q;

#define MAXN 300010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

stack<int> s;

int minv[MAXN],maxv[MAXN],dcc = 0;

int f[MAXN];

long long sum[MAXN];

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

			if(low[e[i].to] >= dfn[k])

			{

				++dcc;

				minv[dcc] = maxv[dcc] = k;

				int t;

				int cnt = 1;

				do

				{

					t = s.top();s.pop();

					minv[dcc] = min(minv[dcc],t);

					maxv[dcc] = max(maxv[dcc],t);

					++cnt;

				}while(t != e[i].to);

				if(cnt != 2)f[minv[dcc]] = maxv[dcc] - 1;

			}

		}

		else

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	return;

}

long long calc(int L,int R)

{

	int l = L - 1,r = R,mid;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(f[mid] <= R)l = mid;

		else r = mid - 1;

	}

	return (sum[l] - sum[L - 1] + 1ll * (R - l) * R) - 1ll * (L + R - 2) * (R - L + 1) / 2;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)add(rd(),rd());

	for(int i = 1;i <= n;++i)f[i] = n;

	for(int i = 1;i <= n;++i)

	{

		if(dfn[i] == 0)tarjan(i);

	}

	for(int i = n - 1;i >= 1;--i)

	{

		f[i] = min(f[i],f[i + 1]);

	}

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + f[i];

	int l,r;

	scanf("%d",&q);

	for(int i = 1;i <= q;++i)

	{

		l = rd();r = rd();

		printf("%lld\n",calc(l,r));

	}

	return 0;

}