- P134's solution
P134's Solution
- 2025-9-14 21:08:37 @
将询问离线下来,按右端点排序,用 LCT 维护割边并用树状数组查询即可。
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 0; char ch = getchar();
while (ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
while (ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
int __stk[128], __top;
inline void write(int x) {
if(x < 0) putchar('-'), x = -x;
do { __stk[++__top] = x % 10, x /= 10; } while (x);
while (__top) putchar(__stk[__top--] + '0');
}
const int mod = 998244353;
void Min(int &x, int y) { y < x and (x = y); }
void Max(int &x, int y) { y > x and (x = y); }
void inc(int &x, int y) { (x += y) >= mod and (x -= mod); }
void mul(int &x, int y) { x = 1ll * x * y % mod; }
int q_pow(int x, int k) { int res = 1; for (; k; k >>= 1, mul(x, x)) if (k & 1) mul(res, x); return res; }
bool stmer;
const int N = 4e5 + 10;
struct edge {
int u, v;
} e[N];
struct Query {
int l, id;
};
int n, m, q;
int ans[N];
vector<Query> op[N];
namespace BIT {
int t[N];
void add(int x, int k) { while (x) t[x] += k, x -= x & -x; }
int ask(int x) { int res = 0; while (x <= m) res += t[x], x += x & -x; return res; }
}
namespace LCT {
int top;
int fa[N], t[N][2], a[N], s[N], tag[N];
int stk[N];
bool nrt(int x) { return t[fa[x]][0] == x or t[fa[x]][1] == x; }
int get(int x) { return t[fa[x]][1] == x; }
void reverse(int x) { swap(t[x][0], t[x][1]), tag[x] ^= 1; }
void pushdown(int x) { if (tag[x]) reverse(t[x][0]), reverse(t[x][1]), tag[x] = 0; }
void update(int x) { s[x] = min({ s[t[x][0]], s[t[x][1]], a[x] }); }
void rotate(int x) {
int f1 = fa[x], f2 = fa[f1], k = get(x);
if (nrt(f1)) t[f2][get(f1)] = x; fa[x] = f2;
t[f1][k] = t[x][!k], fa[t[f1][k]] = f1;
t[x][!k] = f1, fa[f1] = x;
update(f1), update(x);
}
void splay(int x) {
int p = stk[++top] = x;
while (nrt(p)) stk[++top] = p = fa[p];
while (top) pushdown(stk[top--]);
for (int f = fa[x]; nrt(x); rotate(x), f = fa[x])
if (nrt(f)) rotate(get(x) == get(f) ? f : x);
}
void access(int x) {
int f = 0;
while (x) splay(x), t[x][1] = f, update(x), f = x, x = fa[x];
}
void mkrt(int x) { access(x), splay(x), reverse(x); }
void split(int u, int v) { mkrt(u), access(v), splay(v); }
int findrt(int x) {
access(x), splay(x);
while (t[x][0]) pushdown(x), x = t[x][0];
splay(x); return x;
}
void link(int u, int v) { mkrt(u), fa[u] = v; }
void cut(int u, int v) { split(u, v), fa[u] = t[v][0] = 0, update(v); }
bool check(int u, int v) { mkrt(u); return findrt(v) == u; }
void init() {
for (int i = 0; i <= n + m; i++) {
fa[i] = t[i][0] = t[i][1] = BIT :: t[i] = 0;
s[i] = a[i] = i <= n ? n + m + 1 : i;
}
}
}
void solve() {
n = read(), m = read(), q = read(), LCT :: init();
for (int i = 1; i <= m; i++) e[i] = { read(), read() };
for (int i = 1; i <= q; i++) {
int l = read(), r = read();
op[r].push_back({ l, i });
}
for (int i = 1; i <= m; i++) {
int u = e[i].u, v = e[i].v;
if (LCT :: check(u, v) and u != v) {
LCT :: split(u, v);
int x = LCT :: s[v] - n; BIT :: add(x, -1);
LCT :: cut(e[x].u, x + n), LCT :: cut(e[x].v, x + n);
}
if (u ^ v) {
BIT :: add(i, 1);
LCT :: link(u, i + n);
LCT :: link(i + n, v);
}
for (Query l : op[i]) ans[l.id] = n - BIT :: ask(l.l);
op[i].clear();
}
for (int i = 1; i <= q; i++) write(ans[i]), putchar('\n');
}
bool edmer;
signed main() {
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
int T = 1; while(T--) solve();
cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds\n";
return 0;
}