Description
琥珀色黄昏像糖在很美的远方，思念跟影子在傍晚一起被拉长……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}
分析：我们先 DFS 出图的每一个环，得到环上编号最小和最大的节点，那么合法的区间一定不 能同时跨过这两个点。于是我们搞出一个 R 数组，R[i] 表示以 i 作为左端点时右端点最右可 以到哪个位置。R 数组显然是单调递增的。 对于询问 l, r，我们二分出一个位置 i 满足 R[l . . . i − 1] ≤ r,R[i . . . r] ≥ r，直接计算即可。
代码
#include <cstdio> #include <algorithm> #define N 500000 #define ll long long using namespace std; struct arr { int to,nxt,num; }a[N * 2]; struct cir { int l,r; }b[N],h[N]; int n,m,l,ls[N],f[N],can[N]; int vis[N],circle[N],tot; int dfn[N],low[N],s[N],cnt,top; ll sum[N]; bool fl; int cmp(cir x, cir y){return x.r < y.r;} void add(int x, int y, int i) { a[++l].to = y; a[l].nxt = ls[x]; a[l].num = i; ls[x] = l; } void tarjan(int u, int fa) { dfn[u] = low[u] = ++cnt; s[++top] = u; for (int i = ls[u]; i; i = a[i].nxt) if (a[i].to != fa) if (!dfn[a[i].to]) { tarjan(a[i].to, u); low[u] = min(low[u], low[a[i].to]); if (dfn[u] <= low[a[i].to]) { int minn = 1e9, maxx = 0, tmp = top; while (top) { int x = s[top--]; maxx = max(maxx, x); minn = min(minn, x); if (x == a[i].to) break; } maxx = max(maxx, s[top]); minn = min(minn, s[top]); if (tmp - top > 1) can[minn] = min(maxx - 1, can[minn]); } } else low[u] = min(low[u], dfn[a[i].to]); } int main() { freopen("graph4.in","r",stdin); // freopen("graph.out","w",stdout); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); add(x, y, i); add(y, x, i); } for (int i = 1; i <= n; i++) can[i] = n; for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0); for (int i = n - 1; i >= 1; i--) can[i] = min(can[i], can[i + 1]); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (ll)(can[i] - i + 1); int q; scanf("%d", &q); while (q--) { int x, y; ll ans = 0; scanf("%d%d", &x, &y); int L = x, R = y, pos; while (L <= R) { int mid = (L + R) / 2; if (can[mid] >= y) pos = mid, R = mid - 1; else L = mid + 1; } ans = sum[pos - 1] - sum[x - 1]; ans += (ll)(2 + y - pos) * (y - pos + 1) / 2; printf("%lld\n", ans); } }