因为图中只存在奇数长度的环， 所以它是个只有奇数环的仙人掌， 每条边只属于一个环。
那么我们能把所有环给扣出来， 所以我们询问的区间不能包含每个环里的最大值和最小值，
这个东西能用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 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, m, q, to[N], f[N][], mx[N][], mn[N][], 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 << ], lazy[N << ];
inline void pull(int rt) {
a[rt] = a[rt << ] + a[rt << | ];
}
inline void push(int rt, int l, int mid, int r) {
if(lazy[rt]) {
a[rt << ] += lazy[rt] * (mid - l + );
a[rt << | ] += lazy[rt] * (r - mid);
lazy[rt << ] += lazy[rt];
lazy[rt << | ] += lazy[rt];
lazy[rt] = ;
}
}
void update(int L, int R, LL val, int l, int r, int rt) {
if(l >= L && r <= R) {
a[rt] += val * (r - l + );
lazy[rt] += val;
return;
}
int mid = l + r >> ;
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 >> ;
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] + ;
f[u][] = fa;
mx[u][] = u, mn[u][] = u;
for(int i = ; i < ; i++) {
f[u][i] = f[f[u][i - ]][i - ];
mx[u][i] = max(mx[u][i - ], mx[f[u][i - ]][i - ]);
mn[u][i] = min(mn[u][i - ], mn[f[u][i - ]][i - ]);
}
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 = ; i >= ; i--) {
if(depth[u] - depth[v] >= ( << i)) {
MX = max(MX, mx[u][i]);
MN = min(MN, mn[u][i]);
u = f[u][i];
}
}
to[MN] = MX - ;
} 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 = ; i <= n; i++) to[i] = n;
for(int i = ; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = ; i <= n; i++)
if(!vis[i]) dfs(i, );
memset(vis, , sizeof(vis));
for(int i = ; i <= n; i++)
if(!vis[i]) getTo(i, );
for(int i = n - ; i >= ; i--)
to[i] = min(to[i], to[i + ]);
scanf("%d", &q);
for(int i = ; i <= q; i++) {
int L, R; scanf("%d%d", &L, &R);
qus[L].push_back(mk(R, i));
}
for(int i = n; i >= ; i--) {
update(i, to[i], , , n, );
for(auto& Q : qus[i]) ans[Q.se] = query(i, Q.fi, , n, );
}
for(int i = ; i <= q; i++) printf("%lld\n", ans[i]);
return ;
} /*
*/