因为图中只存在奇数长度的环, 所以它是个只有奇数环的仙人掌, 每条边只属于一个环。
那么我们能把所有环给扣出来, 所以我们询问的区间不能包含每个环里的最大值和最小值,
这个东西能用dfs直接扣, 找最大值和最小值能用倍增, 或者直接tarjan扣出来就好。 然后
我们可以处理出每个点开始往右延伸的最大位置, 求答案能离线线段树(我是这么写的),
但有一点就是这个数组是个单调的数组, 所以我们能二分出那个刚好超过R的位置, 直接求就好啦。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std; const int N = 3e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-8; const double PI = acos(-1); int n, m, q, to[N], f[N][20], mx[N][20], mn[N][20], depth[N]; bool vis[N]; LL ans[N]; vector<int> G[N]; vector<PII> qus[N]; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 LL a[N << 2], lazy[N << 2]; inline void pull(int rt) { a[rt] = a[rt << 1] + a[rt << 1 | 1]; } inline void push(int rt, int l, int mid, int r) { if(lazy[rt]) { a[rt << 1] += lazy[rt] * (mid - l + 1); a[rt << 1 | 1] += lazy[rt] * (r - mid); lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; lazy[rt] = 0; } } void update(int L, int R, LL val, int l, int r, int rt) { if(l >= L && r <= R) { a[rt] += val * (r - l + 1); lazy[rt] += val; return; } int mid = l + r >> 1; push(rt, l, mid, r); if(L <= mid) update(L, R, val, lson); if(R > mid) update(L, R, val, rson); pull(rt); } LL query(int L, int R, int l, int r, int rt) { if(l >= L && r <= R) return a[rt]; int mid = l + r >> 1; push(rt, l, mid, r); if(R <= mid) return query(L, R, lson); else if(L > mid) return query(L, R, rson); else return query(L, R, lson) + query(L, R, rson); } void dfs(int u, int fa) { vis[u] = true; depth[u] = depth[fa] + 1; f[u][0] = fa; mx[u][0] = u, mn[u][0] = u; for(int i = 1; i < 20; i++) { f[u][i] = f[f[u][i - 1]][i - 1]; mx[u][i] = max(mx[u][i - 1], mx[f[u][i - 1]][i - 1]); mn[u][i] = min(mn[u][i - 1], mn[f[u][i - 1]][i - 1]); } for(auto& v : G[u]) { if(v == fa || vis[v]) continue; dfs(v, u); } } void getVal(int u, int v) { int MX = v, MN = v; for(int i = 19; i >= 0; i--) { if(depth[u] - depth[v] >= (1 << i)) { MX = max(MX, mx[u][i]); MN = min(MN, mn[u][i]); u = f[u][i]; } } to[MN] = MX - 1; } void getTo(int u, int fa) { vis[u] = true; for(auto& v : G[u]) { if(v == fa) continue; else if(!vis[v]) getTo(v, u); else if(vis[v]) { if(depth[u] > depth[v]) getVal(u, v); } } } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) to[i] = n; for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i, 0); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) if(!vis[i]) getTo(i, 0); for(int i = n - 1; i >= 1; i--) to[i] = min(to[i], to[i + 1]); scanf("%d", &q); for(int i = 1; i <= q; i++) { int L, R; scanf("%d%d", &L, &R); qus[L].push_back(mk(R, i)); } for(int i = n; i >= 1; i--) { update(i, to[i], 1, 1, n, 1); for(auto& Q : qus[i]) ans[Q.se] = query(i, Q.fi, 1, n, 1); } for(int i = 1; i <= q; i++) printf("%lld ", ans[i]); return 0; } /* */