题解
没有偶环，则原图为仙人掌，一个简单环可以对应到有且仅有一个点双。
二分图的充要条件即没有奇环，则 ([x,y]) 中不存在二分图的条件为不存在环。
则求一遍点双之后，对于每一个询问 ([l,r])，设 (nxt_i) 为 ([i,r]) 中以 (i) 为 (x) 时，(y) 的最大值。
先考虑如何求 (nxt_i)。对于每一个简单环，设环内最小结点编号为 (mn)，最大结点编号为 (mx)，则令 (nxt_{mn} gets min { nxt_{mn}, mx })。然后从 (r) 到 (l) 求后缀最小值，即 (nxt_i gets min { nxt_i, nxt_{i+1} })。
然后考虑如何算贡献。对于 (nxt_i leq r)，以 (i) 为 (x) 时，对 ([x,y]) 方案数的贡献为 (nxt_i - i)。对于 (nxt_i > r)，以 (i) 为 (x) 时，对 ([x,y]) 方案数的贡献为 (r - i + 1)。
显然 (nxt_i) 是单调的，那么可以二分求出最大的 (i) 满足 (nxt_i leq r)。对于第一种情况，用一个前缀和预处理。对于第二种情况，显然贡献为一个等差数列，直接算即可。
注意二分边界！！！
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAX_N (300000 + 5)
#define MAX_M (300000 + 5)
using std::max;
using std::min;
int n, m, q;
int h[MAX_N], tot;
struct Edge {
int to, next;
} e[MAX_M * 2];
int dfn[MAX_N], low[MAX_N], cnt;
int st[MAX_N], tp;
int nxt[MAX_N];
long long sum[MAX_N];
void Read(int &x) {
x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
}
void Write(long long x) {
if (x >= 10) Write(x / 10);
putchar(x % 10 + '0');
}
void AddEdge(int u, int v) {
e[++tot].to = v;
e[tot].next = h[u];
h[u] = tot;
}
void Tarjan(int u) {
dfn[u] = low[u] = ++cnt;
st[++tp] = u;
int v;
for (int i = h[u]; i; i = e[i].next) {
v = e[i].to;
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v]) {
int mn = u, mx = u, tmp = 1;
while (st[tp] != u) {
++tmp;
mn = min(mn, st[tp]);
mx = max(mx, st[tp]);
--tp;
}
if (tmp >= 3) nxt[mn] = min(nxt[mn], mx);
}
}
else low[u] = min(low[u], dfn[v]);
}
}
int main() {
Read(n), Read(m);
int u, v;
for (int i = 1; i <= m; ++i) Read(u), Read(v), AddEdge(u, v), AddEdge(v, u);
for (int i = 1; i <= n; ++i) nxt[i] = n + 1;
for (int i = 1; i <= n; ++i) if (!dfn[i]) Tarjan(i);
for (int i = n - 1; i; --i) nxt[i] = min(nxt[i + 1], nxt[i]);
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + nxt[i] - i;
Read(q);
int ql, qr, l, r, mid;
long long ans;
while (q--) {
Read(ql), Read(qr);
l = ql - 1, r = qr;
while (l < r) {
mid = l + r + 1 >> 1;
if (nxt[mid] > qr) r = mid - 1;
else l = mid;
}
ans = sum[r] - sum[ql - 1] + (long long)(qr - r + 1) * (qr - r) / 2;
Write(ans), putchar('
');
}
return 0;
}