Codeforces 901C Bipartite Segments（Tarjan + 二分）

题目链接  Bipartite Segments

题意  给出一个无偶环的图，现在有$q$个询问。求区间$[L, R]$中有多少个子区间$[l, r]$

　　满足$L <= l <= r <= R$，并且一个只包含$l$到$r$这些点的无向图为二分图。

因为整张图没有偶环，所以在这道题中如果某个无向图没有环，那个这个无向图就是二分图

Tarjan求出每个环的标号最小点和标号最大点。

令$f[i]$为能保证$[i, j]$这个区间构成的图都是二分图的$j$的最大值，则$f[i]$是不下降的

当询问区间$[L, R]$的时候，即求$\begin{equation*}\sum_{i=L}^Rmin(f(i), R) – i + 1\end{equation*}$

二分然后分类讨论即可

#include <bits/stdc++.h>using namespace std;#define rep(i, a, b)for (int i(a); i <= (b); ++i)
#define dec(i, a, b)for (int i(a); i >= (b); --i)typedef long long LL;const int N = 3e5 + 10;int f[N], dfn[N], stk[N];
int n, m, ti = 0;
int q, top;
LL s[N];
vector <int> v[N];void dfs(int x, int fa){
dfn[x] = ++ti;
stk[++top] = x;
for (auto u : v[x]){
if (u == fa) continue;
if (dfn[u]){
if (dfn[u] < dfn[x]){
int mx = u, mi = u;
for (int p = top; stk[p] != u; --p){
mi = min(mi, stk[p]);
mx = max(mx, stk[p]);
}
f[mi] = mx;
}
}
else dfs(u, x);
}
--top;
}int main(){scanf("%d%d", &n, &m);
rep(i, 1, m){
int x, y;
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}rep(i, 1, n) if (!dfn[i]) dfs(i, 0);
rep(i, 1, n) if (f[i]) --f[i]; else f[i] = n;
dec(i, n - 1, 1) f[i] = min(f[i], f[i + 1]);
rep(i, 1, n) s[i] = s[i - 1] + f[i];scanf("%d", &q);
while (q--){
int x, y;
scanf("%d%d", &x, &y);
if (f[x] > y){
LL num = y - x + 1;
printf("%lld\n", 0ll - 1ll * (x + y) * num / 2 + 1ll * y * num + num);
continue;
}int l = x, r = y;
while (l + 1 < r){
int mid = (l + r) >> 1;
if (f[mid] <= y) l = mid; else r = mid - 1;
}int t;
if (f[r] <= y) t = r; else t = l;int u = t + 1;
LL num = y - x + 1;
LL ans = num - 1ll * (x + y) * num / 2;LL et = y - u + 1;
ans = ans + (s[t] - s[x - 1]);
if (et > 0) ans = ans + 1ll * y * et;
printf("%lld\n", ans);}
return 0;
}