Codechef 14.3 GERALD07 LCT+可持久化线段树
题目大意：
给定一张$n$个点$m$条边的无向图，图中可能存在重边和自环，现在有$q$个询问，每次询问只保留标号在$[l,r]$区间内的边时，图中连通块的个数。
数据范围$n,m,q\leq{2\times{10^5}}$。
算法讨论：
一开始有$n$个连通块，对于一个区间中的边，那些两个端点之前没有连通的边，加入后会使得连通块的数目减少1。
所以我们只需知道哪些边是在加入这条边之前两个端点不连通的。
我们按照标号加入每条边，维护关于标号的最大生成树，并在加入这条边的时候，记录删掉了哪条边。
考虑区间$[l,r]$中的一条边$x$，若其弹掉了边$y$，则证明必须加入$y$这条边以及若干条之后的边，$x$的两个端点才能连通。因此，若$y<l$，则此时$x$的两个端点不连通，对答案产生$-1$的贡献；否则$y\leq{l}$，说明$[l,r]$中只使用$x$之前的某些边已经能让$x$的两个端点连通，对答案没有贡献。
使用Link-Cut Tree维护每个点弹掉了哪条边，对于每次询问其实就是询问区间$[l,r]$中弹掉边的标号$<l$的边的数目，可以用可持久化线段树维护。
时间复杂度$O((n+m+q)\log n)$。
时空复杂度：
时间复杂度$O((n+m+q)\log n)$，空间复杂度$O(n+m\log m+q)$。
代码：
#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
inline int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) { T = (S = buf) + fread(buf, 1, L, stdin); if (S == T) return EOF; }
return *S++;
}
inline int getint() {
int c;
while(!isdigit(c = getc()));
int tmp = c - '0';
while(isdigit(c = getc()))
tmp = (tmp << 1) + (tmp << 3) + c - '0';
return tmp;
}
char buf[2000000], *o = buf;
void output(int x) {
static int stack[100];
int top = 0;
for(; x; x /= 10)
stack[++top] = 48 + x % 10;
for(int i = top; i >= 1; --i)
*o++ = stack[i];
*o++ = '\n';
}
#define INF 0x3f3f3f3f
#define N 200010
#define M 200010
#define l ch[0]
#define r ch[1]
struct Node {
Node *ch[2], *pa;
int lab, Min;
bool rev;
Node():Min(INF),rev(0){}
bool d() { return this == pa->r; }
bool isRoot() { return this != pa->l && this != pa->r; }
inline void sc(Node* p, bool d) { ch[d] = p, p->pa = this; }
void RevIt() { rev ^= 1, swap(l, r); }
void up();
void down();
}Tnull, *null = &Tnull, mem[N + M], *C = mem, *Edge[M], *Point[N];
Node* Newnode(int _lab) {
C->l = C->r = C->pa = null;
C->lab = C->Min = _lab;
C->rev = 0;
return C++;
}
void Node::up() {
Min = lab;
if (l != null) Min = min(Min, l->Min);
if (r != null) Min = min(Min, r->Min);
}
void Node::down() {
if (rev) {
if (l != null) l->RevIt();
if (r != null) r->RevIt();
rev = 0;
}
}
void PushPath(Node *q) {
static Node* stack[N + M];
int top = 0;
while(!q->isRoot())
stack[++top] = q, q = q->pa;
stack[++top] = q;
for(int i = top; i >= 1; --i)
stack[i]->down();
}
void Rot(Node *q) {
Node *f = q->pa;
bool d = q->d();
q->pa = f->pa;
if (!f->isRoot())
f->pa->ch[f->d()] = q;
f->sc(q->ch[!d], d);
f->up();
q->sc(f, !d);
}
void Splay(Node *q) {
PushPath(q);
while(!q->isRoot()) {
if (q->pa->isRoot())
Rot(q);
else
Rot(q->d() == q->pa->d() ? q->pa : q), Rot(q);
}
q->up();
}
void Access(Node *q) {
Node *p = null;
while(q != null) {
Splay(q);
q->r = p;
q->up();
p = q, q = q->pa;
}
}
void Makeroot(Node *q) {
Access(q);
Splay(q);
q->RevIt();
}
void Link(Node *p, Node *q) {
Makeroot(p);
p->pa = q;
}
void Cut(Node *p, Node* q) {
Makeroot(p);
Access(q);
Splay(q);
q->l = p->pa = null;
q->up();
}
Node* FindRoot(Node *q) {
while(q->pa != null)
q = q->pa;
return q;
}
int GetMin(Node *p, Node *q) {
Makeroot(p);
Access(q);
Splay(q);
return q->Min;
}
#define l(x) S[x].l
#define r(x) S[x].r
#define size(x) S[x].size
struct Seg {
int l, r, size;
}S[4000010];
int id;
int root[M];
int NewVersion(int Last, int dl, int dr, int ins) {
int q = ++id;
S[q] = S[Last];
++size(q);
if (dl == dr)
return q;
int mid = (dl + dr) >> 1;
if (ins <= mid)
l(q) = NewVersion(l(Last), dl, mid, ins);
else
r(q) = NewVersion(r(Last), mid + 1, dr, ins);
return q;
}
int CalcLess(int Left, int Right, int dl, int dr, int ins) {
int res = 0, mid;
while(1) {
if (dl == dr) {
res += ((dl < ins) ? 1 : 0);
break;
}
mid = (dl + dr) >> 1;
if (mid >= ins)
dr = mid, Left = l(Left), Right = l(Right);
else
dl = mid + 1, res += size(l(Right)) - size(l(Left)), Left = r(Left), Right = r(Right);
}
return res;
}
int w[N];
void init() {
C = mem;
id = 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
int T = getint(), n, m, q;
while (T--) {
init();
n = getint(), m = getint(), q = getint();
register int i;
for(i = 1; i <= n; ++i)
Point[i] = Newnode(INF);
int a, b;
memset(w, 0, sizeof w);
for(i = 1; i <= m; ++i) {
a = getint(), b = getint();
if (a == b) {
w[i] = i;
continue;
}
Edge[i] = Newnode(i);
if (FindRoot(Point[a]) == FindRoot(Point[b])) {
int del = GetMin(Point[a], Point[b]);
w[i] = del;
Cut(Point[a], Edge[del]);
Cut(Point[b], Edge[del]);
}
Link(Point[a], Edge[i]);
Link(Point[b], Edge[i]);
}
for(i = 1; i <= m; ++i)
root[i] = NewVersion(root[i - 1], 1, m + 1, w[i] + 1);
int lastans = 0;
while(q--) {
a = getint(), b = getint();
output(lastans = n - CalcLess(root[a - 1], root[b], 1, m + 1, a + 1));
}
}
return fwrite(buf, 1, o - buf, stdout), 0;
}
评论 (0)