N个点M条边的无向图, K个询问, 问保留图中编号在[l,r]的边的时候图中的连通块个数. 强制在线. (1≤N,M,K≤200,000) 很妙的一道题. 睡午觉之前看的题面, 起来之后又想了一会儿, 就看题解了......
如果要求一个无向图的连通块个数, 可以这样做: 初始答案为n, 用并查集维护连通块, 每连接两个不同的连通块, 答案-1. 也就是说, 有一些边对答案产生-1的贡献, 另一些不产生贡献. 无贡献的边并非永远没有贡献. 考虑第一条会形成环的边. 如果保留的区间包含这条边, 而不包含环上编号最小的边, 则这条边仍然会产生-1的贡献. "第一条" 的含义是, 先前的边对答案都是有贡献的. 不妨删除环上编号最小的边, 连上这条本会形成环的边. 重复这个过程, 我们总是可以进行上述推理.
综上, 算法流程是: 动态加边, 维护生成森林, 如果第i条边连接两个不同的连通块, 则num[i] = 0; 否则, 如果第i条边是自环, 它永远不会产生贡献, 令num[i] = i; 否则, 删掉环上编号最小的边mn, 令num[i]=mn, 并加入这条新的边. 用可持久化线段树等回答num[l,r]有多少小于l的数, n减去它, 即为答案.
不知道怎么严格地证明正确性, 在网上也没找到比较严谨的, 只好先脑补了......
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
using namespace std;
const int inf = 1e8, N = 200000, M = 200000, LG_M = 18;
namespace LCT {
struct Node {
Node* ch[2], * fa, * mn;
int v, t;
bool rev;
Node();
void up()
{
mn = this;
if (ch[0]->mn->v < v)
mn = ch[0]->mn;
if (ch[1]->mn->v < mn->v)
mn = ch[1]->mn;
}
void reverse()
{
rev = !rev;
swap(ch[0], ch[1]);
ch[0]->t = 0;
ch[1]->t = 1;
}
void down()
{
if (rev) {
rev = false;
ch[0]->reverse();
ch[1]->reverse();
}
}
void setf(Node* f, int t1)
{
fa = f;
t = t1;
t >= 0 ? f->ch[t] = this : 0;
}
} nodes[1 + N + M], * nil = nodes;
Node::Node(): fa(nil), mn(this), v(inf), t(-1), rev(false)
{
ch[0] = ch[1] = nil;
}
inline void rot(Node* y)
{
Node* x = y->fa;
int t = y->t;
y->setf(x->fa, x->t);
y->ch[t^1]->setf(x, t);
x->setf(y, t^1);
x->up();
}
void splay(Node* x)
{
Node* y;
static Node* S[N + M];
int top = 0;
for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
for (y->down(); top; S[--top]->down()) ;
while (x->t >= 0) {
if ((y = x->fa)->t >= 0)
rot(x->t ^ y->t ? x : y);
rot(x);
}
x->up();
}
void access(Node* x)
{
for (Node* y = nil; x != nil; y = x, x = x->fa) {
splay(x);
x->ch[1]->t = -1;
y->setf(x, 1);
x->up();
}
}
inline void make_root(Node* x)
{
access(x);
splay(x);
x->reverse();
}
inline void link(Node* x, Node* y)
{
make_root(x);
x->setf(y, -1);
}
inline void cut(Node* x, Node* y)
{
make_root(y);
access(x);
splay(x);
x->ch[0]->setf(nil, -1);
x->ch[0] = nil;
x->up();
}
inline Node& path(Node* x, Node* y)
{
make_root(x);
access(y);
splay(y);
return *y;
}
}
namespace UF {
int f[N + 1], rk[N + 1];
int F(int x)
{
return f[x] ? f[x] = F(f[x]) : x;
}
inline void merge(int x, int y)
{
if (rk[y] > rk[x]) swap(x, y);
f[y] = x;
rk[x] += rk[x] == rk[y];
}
}
namespace Seg {
struct Node {
Node* lc, * rc;
int v;
Node();
Node(const Node& v) { *this = v; }
void* operator new(size_t);
} nodes[(1 + LG_M)*(M + 1) + 1], * root[M + 1], * nil = nodes, * cur = nodes + 1;
Node::Node(): lc(nil), rc(nil), v(0) {}
void* Node::operator new(size_t) { return cur++; }
void insert(Node* &o, Node* p, int x, int l, int r)
{
o = new Node(*p);
++o->v;
if (l != r) {
int m = (l+r)/2;
if (x <= m)
insert(o->lc, p->lc, x, l, m);
else
insert(o->rc, p->rc, x, m+1, r);
}
}
// [1, x]
int query(Node* o, Node* p, int x, int l, int r)
{
if (r <= x)
return o->v - p->v;
int m = (l+r)/2;
return query(o->lc, p->lc, x, l, m) + (x > m ? query(o->rc, p->rc, x, m+1, r) : 0);
}
void build(int A[], int n)
{
root[0] = nil;
For (i, 1, n)
insert(root[i], root[i-1], A[i], 0, n);
}
inline int query(int l, int r, int n)
{
return query(root[r], root[l-1], l-1, 0, n);
}
}
int num[M+1];
int main()
{
using namespace UF;
using namespace LCT;
int n, m, k, type;
scanf("%d%d%d%d", &n, &m, &k, &type);
For (i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
int ru = F(u), rv = F(v);
if (u == v) {
num[i] = i;
continue;
}
Node* x = nodes + u, * y = nodes + v, * z = nodes + n + i;
z->v = i;
if (ru != rv) {
merge(ru, rv);
num[i] = 0;
} else {
Node* e = path(x, y).mn;
num[i] = e->v;
cut(e, x);
cut(e, y);
}
link(z, x);
link(z, y);
}
Seg::build(num, m);
int lastans = 0;
while (k--) {
int l, r;
scanf("%d%d", &l, &r);
if (type) {
l ^= lastans;
r ^= lastans;
}
lastans = n - Seg::query(l, r, m);
printf("%d\n", lastans);
}
return 0;
}