Solution
因为这是一个仙人掌图，所以我们可以通过(tarjan)缩点双找出图中所有的简单环。然后我们找出每一个环中的最大编号和最小编号，并按最大编号从小到大排序。然后我们把询问离线下来，并且挂在询问的右端点处
然后我们从左往右扫，处理每一个节点处的询问之前，先把最左能走的不会形成环的位置更新出来。然后用线段树把这一段区间加(1)
询问就直接再线段树上区间求和就行了
还有一种做法，就是直接预处理出每一个点最左能走的不会形成环的位置，记为(pos[i])。对于查询([l, r])，二分找到最小的(i)使得(pos[i] > l)。然后我们分别对([l, i - 1])和([i, r])计算贡献，加起来就可以了
Code
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef pair<int, int> pii;
inline int read() {
int sum = 0, fg = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') fg = -1;
for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
return fg * sum;
}
const int maxn = 3e5 + 10;
vector<int> g[maxn];
vector<pii> v[maxn];
int d[maxn], low[maxn], pre[maxn], dfn;
int S[maxn], top, cnt, n, m, q;
pii p[maxn];
LL ans[maxn];
void tarjan(int now, int f) {
d[now] = low[now] = ++dfn;
S[++top] = now;
for (int i = 0; i < g[now].size(); i++) {
int son = g[now][i];
if (son == f) continue;
if (!d[son]) {
tarjan(son, now);
low[now] = min(low[now], low[son]);
if (low[son] >= d[now]) {
int Max = 0, Min = n + 1, tot = 0;
while (top) {
int x = S[top--];
Max = max(Max, x);
Min = min(Min, x);
++tot;
if (x == son) break;
}
Max = max(Max, now), Min = min(Min, now);
if (tot > 1) p[++cnt] = (pii){Max, Min};
}
}else low[now] = min(low[now], d[son]);
}
}
namespace ST {
LL A[maxn << 2], tag[maxn << 2];
#define ls (rt << 1)
#define rs (rt << 1 | 1)
void push_up(int rt) { A[rt] = A[ls] + A[rs]; }
void push_down(int rt, int l, int r) {
if (!tag[rt]) return;
int mid = (l + r) >> 1;
tag[ls] += tag[rt];
tag[rs] += tag[rt];
A[ls] += tag[rt] * (mid - l + 1);
A[rs] += tag[rt] * (r - mid);
tag[rt] = 0;
}
void change(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) {
A[rt] += r - l + 1, ++tag[rt]; return;
}
push_down(rt, l, r);
int mid = (l + r) >> 1;
if (L <= mid) change(ls, l, mid, L, R);
if (R > mid) change(rs, mid + 1, r, L, R);
push_up(rt);
}
LL query(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) return A[rt];
push_down(rt, l, r);
int mid = (l + r) >> 1; LL res = 0;
if (L <= mid) res += query(ls, l, mid, L, R);
if (R > mid) res += query(rs, mid + 1, r, L, R);
return res;
}
}
int main() {
#ifdef xunzhen
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
#endif
n = read(), m = read();
for (int i = 1; i <= m; i++) {
int x = read(), y = read();
g[x].push_back(y);
g[y].push_back(x);
}
q = read();
for (int i = 1; i <= q; i++) {
int x = read(), y = read();
v[y].push_back((pii){x, i});
}
for (int i = 1; i <= n; i++) if (!d[i]) tarjan(i, 0);
sort(p + 1, p + cnt + 1);
int j = 1, Max = 0;
for (int i = 1; i <= n; i++) {
while (j <= cnt && p[j].fst <= i) Max = max(Max, p[j++].snd);
ST::change(1, 1, n, Max + 1, i);
for (int j = 0; j < v[i].size(); j++)
ans[v[i][j].snd] = ST::query(1, 1, n, v[i][j].fst, i);
}
for (int i = 1; i <= q; i++) printf("%lld
", ans[i]);
return 0;
}
Summary
考试的时候没有注意到这是一个仙人掌，以为这是一个仙人球，然后我就打了一个缩边双...