HDU - 5333 Undirected Graph LCT

HDU - 5333

感觉这个转换成维护最大生成树的方法很巧妙呀， 离线转化之后就是一个裸的LCT维护最大生成树， 用BIT统计边。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define ull unsigned 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 ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
const int N = 3e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1);
template<class T, class S> inline void add(T &a, S b) {a += b; if(a >= mod) a -= mod;}
template<class T, class S> inline void sub(T &a, S b) {a -= b; if(a < 0) a += mod;}
template<class T, class S> inline bool chkmax(T &a, S b) {return a < b ? a = b, true : false;}
template<class T, class S> inline bool chkmin(T &a, S b) {return a > b ? a = b, true : false;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, q;
int ans[N];
vector<int> E[N];
vector<PII> Q[N];
struct Bit {
int a[N];
void init() {
for(int i = 1; i <= n; i++) {
a[i] = 0;
}
}
inline void modify(int x, int v) {
for(int i = x; i <= n; i += i & -i) {
a[i] += v;
}
}
inline int sum(int x) {
int ans = 0;
for(int i = x; i; i -= i & -i) {
ans += a[i];
}
return ans;
}
inline int query(int L, int R) {
if(L > R) return 0;
return sum(R) - sum(L - 1);
}
} bit;
struct LCT {
#define l(x) (ch[x][0])
#define r(x) (ch[x][1])
int fa[N], ch[N][2], rev[N], sz[N], q[N];
int U[N], V[N];
PII w[N], mn[N];
int tot;
void restore() {
for(int i = 1; i <= tot; i++) {
fa[i] = rev[i] = sz[i] = 0;
ch[i][0] = ch[i][1] = 0;
}
}
void init(int n) {
for(int i = 0; i <= n; i++) {
fa[i] = rev[i] = 0;
sz[i] = 1;
mn[i] = w[i] = mk(1000000, i);
ch[i][0] = ch[i][1] = 0;
}
tot = n + 1;
}
inline bool isroot(int x) {
return l(fa[x]) != x && r(fa[x]) != x;
}
inline void pull(int x) {
sz[x] = sz[l(x)] + sz[r(x)] + 1;
mn[x] = w[x];
chkmin(mn[x], mn[l(x)]);
chkmin(mn[x], mn[r(x)]);
}
inline void push(int x) {
if(rev[x]) {
rev[x] = 0; swap(l(x), r(x));
rev[l(x)] ^= 1; rev[r(x)] ^= 1;
}
}
inline void rot(int x) {
int y = fa[x], z = fa[y], l, r;
if(ch[y][0] == x) l = 0, r = l ^ 1;
else l = 1, r = l ^ 1;
if(!isroot(y)) {
if(l(z) == y) l(z) = x;
else r(z) = x;
}
fa[x] = z; fa[y] = x; fa[ch[x][r]]=y;
ch[y][l] = ch[x][r]; ch[x][r] = y;
pull(y); pull(x);
}
inline void splay(int x) {
int top = 1; q[top] = x;
for(int i = x; !isroot(i); i = fa[i]) q[++top] = fa[i];
for(int i = top; i; i--) push(q[i]);
while(!isroot(x)) {
int y = fa[x], z = fa[y];
if(!isroot(y)) {
if((l(y) == x) ^ (l(z) == y)) rot(x);
else rot(y);
}
rot(x);
}
}
inline void access(int x) {
for(int y = 0; x; y = x, x = fa[x]) {
splay(x);
r(x) = y;
pull(x);
}
}
inline void makeroot(int x) {
access(x); splay(x); rev[x] ^= 1;
}
inline int findroot(int x) {
access(x); splay(x);
while(l(x)) x = l(x);
return x;
}
inline void split(int x, int y) {
makeroot(x); access(y); splay(y);
}
inline void link(int x, int y) {
makeroot(x); fa[x] = y; splay(x);
}
inline void cut(int x, int y) {
split(x, y);
if(l(y) == x) l(y) = 0, fa[x] = 0;
}
void change(int x, int y, int weight) {
if(findroot(x) != findroot(y)) {
++tot;
w[tot] = mk(weight, tot);
mn[tot] = mk(weight, tot);
U[tot] = x; V[tot] = y;
sz[tot] = 1;
link(x, tot);
link(y, tot);
bit.modify(weight, 1);
return;
}
makeroot(x);
access(y);
splay(y);
PII minVal = mn[y];
if(minVal.fi >= weight) return;
cut(minVal.se, V[minVal.se]);
cut(minVal.se, U[minVal.se]);
bit.modify(minVal.fi, -1);
w[minVal.se] = mk(weight, minVal.se);
mn[minVal.se] = mk(weight, minVal.se);
U[minVal.se] = x; V[minVal.se] = y;
sz[minVal.se] = 1;
link(x, minVal.se);
link(y, minVal.se);
bit.modify(weight, 1);
}
} lct;
int main() {
while(scanf("%d%d%d", &n, &m, &q) != EOF) {
bit.init();
lct.restore();
lct.init(n);
for(int i = 1; i <= n; i++) {
E[i].clear();
Q[i].clear();
}
for(int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
if(u > v) swap(u, v);
if(u == v) continue;
E[v].push_back(u);
}
for(int i = 1; i <= q; i++) {
int L, R;
scanf("%d%d", &L, &R);
Q[R].push_back(mk(L, i));
ans[i] = n;
}
for(int i = 2; i <= n; i++) {
for(auto &j : E[i]) {
lct.change(i, j, j);
}
for(auto &q : Q[i]) {
ans[q.se] -= bit.query(q.fi, i);
}
}
for(int i = 1; i <= q; i++) {
printf("%dn", ans[i]);
}
}
return 0;
}