【Codechef】【Chef and Graph Queries】Lct 可持久化线段树

shangban

　　Problem code: GERALD07
　　一个无向图，q次询问，每次询问留下li到ri的边有几个联通块。n, m, q <= 200000.
　　先预处理出每个边能替代之前最早的的边bi使其还是一棵树，用Lct维护。用可持久化线段树查询。
　　#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#define Rep(i, x, y) for (int i = x; i <= y; i ++)
#define RepE(i, x) for (int i = pos[x]; i; i = g.nex)
#define Dwn(i, x, y) for (int i = x; i >= y; i --)
#define u t[x]
#define v t[y]
#define lc u.ch[0]
#define rc u.ch[1]
#define Lc t[lc]
#define Rc t[rc]
#define tp u.par
#define Tp t[tp]
#define su seg[x]
#define sv seg[y]
#define Slc seg[su.lch]
using namespace std;
typedef long long LL;
const int N = 200000 * 4;
struct arr {
int ch[2], par, p, mx, vl; bool rv;
void Clr(int x, int y) { ch[1] = ch[0] = par = rv = 0, p = x, vl = mx = y; }
} t[N*2];
struct Segtree {
int l, r, vl, lch, rch;
void Clr(int lx, int rx) { l = lx, r = rx, vl = lch = rch = 0; }
} seg[N*30];
int n, m, sz, tz, T[N], Q, Test, b[N], val, q, X[N], Y[N], ans;
void Upd(int x) {
if (!x) return ;
int z = min(Lc.mx, Rc.mx);
if (z >= u.vl) u.mx = u.vl, u.p = x;
else (Lc.mx < Rc.mx) ? (u.mx = Lc.mx, u.p = Lc.p) : (u.mx = Rc.mx, u.p = Rc.p);
}
void PD(int x) { if (x && u.rv) Lc.rv ^= 1, Rc.rv ^= 1, swap(lc, rc), u.rv = 0; }
bool d(int x) { return Tp.ch[1] == x; }
bool Sch(int x, int &y) { return (y = tp) && (v.ch[1] == x || v.ch[0] == x); }
void Sc(int x, int y, bool f) { u.ch[f] = y, v.par = x; }
void Rot(int x) {
int y = tp, z, f = d(x);
if (Sch(y, z)) Sc(z, x, d(y));
else u.par = z;
Sc(y, u.ch[!f], f), Sc(x, y, !f), Upd(y);
}
void Splay(int x) {
int y, z;
PD(x);
while (Sch(x, y)) {
PD(v.par), PD(y), PD(x);
if (!Sch(y, z)) Rot(x);
else (d(x) == d(y)) ? (Rot(y), Rot(x)) : (Rot(x), Rot(x));
} Upd(x);
}
int Access(int x) { int y = 0; for (; x; x = tp) Splay(x), rc = y, Upd(y = x); return y; }
void Make(int x) { t[Access(x)].rv ^= 1, Splay(x); }
int Find(int x) {
for (x = Access(x); PD(x), lc; x = lc) ; return x;
}
void Link(int x, int y) { Make(x), tp = y; }
void Cut(int x, int y) { Make(x), Access(y), Splay(y), tp = v.ch[0] = 0, Upd(y); }
void Tqry(int x, int y) {
Make(x); int z = Access(y);
val = t[z].mx, q = t[z].p;
}
int Build(int l, int r) {
int x = ++ tz, mid = (l + r) / 2;
su.Clr(l, r);
if (l == r) return x;
su.lch = Build(l, mid), su.rch = Build(mid + 1, r);
return x;
}
int Add(int y, int z) {
int x = ++ tz, mid = (sv.l + sv.r) / 2; su = sv, su.vl ++;
if (su.l == su.r) return x;
if (z <= mid) su.lch = Add(sv.lch, z);
else su.rch = Add(sv.rch, z);
return x;
}
int Qry(int x, int z) {
int l = su.l, r = su.r, mid = (l + r) / 2;
if (l == r) return su.vl;
if (z > mid) return Slc.vl + Qry(su.rch, z);
else return Qry(su.lch, z);
}
int main()
{
scanf (&quot;%d&quot;, &Test);
while (Test --) {
scanf (&quot;%d%d%d&quot;, &n, &m, &Q);
sz = n, tz = 0;
memset(X, 0, sizeof(X));
memset(Y, 0, sizeof(Y));
Rep(i, 0, n) t.Clr(i, 1 << 28);
Rep(i, 1, m) {
int x, y;
scanf (&quot;%d%d&quot;, &x, &y);
if (x == y) { b = i; continue ; }
if (Find(x) == Find(y)) {
Tqry(x, y), b = val;
Cut(q, X[q]), Cut(q, Y[q]);
} else b = 0;
t[++ sz].Clr(sz, 1 << 28);
X[sz] = x, Y[sz] = y;
Link(sz, x), Link(sz, y), t[sz].vl = i, Splay(sz);
}
T[0] = Build(0, m);
Rep(i, 1, m) {
T = Add(T[i-1], b);
}
Rep(i, 1, Q) {
int x, y;
scanf (&quot;%d%d&quot;, &x, &y);
ans = Qry(T[y], x-1);
ans -= x - 1;
printf (&quot;%d\n&quot;, n - ans);
}
}
return 0;
}