题意
给出nnn个点,mmm条边.多次询问,求编号在[l,r][l,r][l,r]内的边形成的联通块的数量,强制在线.
分析
- LCTLCTLCT维护动态最大生成树，先将每条边依次加进去，若形成环就断掉最早加进去(编号最小)的边，然后记录early[]early[]early[]数组，表示第i条边弹掉了哪条边，若没有弹出边，early[i]=0early[i]=0early[i]=0
- 然后每个询问的答案就是用n减掉[l,r]区间内early值小于l的边的数量,可以用主席树来维护
- 正确性证明:因为是维护的最大生成树,而early[i]early[i]early[i]又是最大生成树中的最小边,那么(early[i],i)(early[i],i)(early[i],i)这些边一定不能让iii的两个端点联通.所以说对于r>=ir>=ir>=i且l>early[i]l>early[i]l>early[i]的询问,如果按编号从小到大加入边,那么在iii之前它的两个端点一定还不联通,加入iii这条边让它们合并成为一个联通块,答案就减一.所以说只要求出所有earlyearlyearly在主席树上维护就行了.
- 注意有自环(良心样例有自环)
CODE
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; for(;!isdigit(ch=getc()););
for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
const int MAXN = 200005;
const int MAXM = MAXN*20;
int n;
namespace LCT {
const int N = 400005;
#define ls ch[x][0]
#define rs ch[x][1]
int ch[N][2], fa[N], mn[N]; bool rev[N];
inline bool isr(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
inline bool get(int x) { return ch[fa[x]][1] == x; }
inline int Max(int x, int y) { if(x <= n) return y; if(y <= n) return x; return min(x, y); }
inline void upd(int x) { mn[x] = Max(x, Max(mn[ls], mn[rs]));}
inline void mt(int x) { if(rev[x]) rev[x]^=1, rev[ls]^=1, rev[rs]^=1, swap(ls, rs); }
void mtpath(int x) { if(!isr(x)) mtpath(fa[x]); mt(x); }
inline void rot(int x) {
int y = fa[x], z = fa[y];
bool l = get(x), r = l^1;
if(!isr(y)) ch[z][get(y)] = x;
fa[ch[x][r]] = y, fa[y] = x, fa[x] = z;
ch[y][l] = ch[x][r], ch[x][r] = y;
upd(y), upd(x);
}
inline void splay(int x) {
mtpath(x);
for(; !isr(x); rot(x))
if(!isr(fa[x])) rot(get(x) == get(fa[x]) ? fa[x] : x);
}
inline int access(int x) { int y = 0;
for(; x; x = fa[y=x]) splay(x), ch[x][1] = y, upd(x);
return y;
}
inline void bert(int x) { access(x), splay(x), rev[x]^=1; }
inline int sert(int x) { access(x), splay(x); for(; ls; x=ls); return x; }
inline bool judge(int x, int y) { bert(x); return sert(y) == x; }
inline void link(int x, int y) { bert(x); fa[x] = y; }
inline void split(int x, int y) { bert(x); access(y), splay(y); }
inline void cut(int x, int y) { split(x, y); ch[y][0] = fa[x] = 0; upd(y); }
inline int findmn(int x, int y) { split(x, y); return mn[y]; }
#undef ls
#undef rs
}
int m, q, type, pre[MAXN], u[MAXN], v[MAXN];
int rt[MAXN], sz, sum[MAXM], ch[MAXM][2];
void modify(int &i, int p, int l, int r, int x) {
if(!i) i = ++sz;
sum[i] = sum[p] + 1;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) ch[i][1] = ch[p][1], modify(ch[i][0], ch[p][0], l, mid, x);
else ch[i][0] = ch[p][0], modify(ch[i][1], ch[p][1], mid+1, r, x);
}
int query(int i, int j, int l, int r, int ql, int qr) {
if(l == ql && r == qr) return sum[j] - sum[i];
int mid = (l + r) >> 1;
if(qr <= mid) return query(ch[i][0], ch[j][0], l, mid, ql, qr);
else if(ql > mid) return query(ch[i][1], ch[j][1], mid+1, r, ql, qr);
return query(ch[i][0], ch[j][0], l, mid, ql, mid) + query(ch[i][1], ch[j][1], mid+1, r, mid+1, qr);
}
int main () {
read(n), read(m), read(q), read(type);
for(int i = 1; i <= m; ++i) {
read(u[i]), read(v[i]);
if(u[i] == v[i]) rt[i] = rt[i-1];
else {
if(LCT::judge(u[i], v[i])) {
int p = LCT::findmn(u[i], v[i]);
pre[i] = p-n;
LCT::cut(u[pre[i]], p);
LCT::cut(v[pre[i]], p);
}
LCT::link(u[i], n+i);
LCT::link(v[i], n+i);
modify(rt[i], rt[i-1], 0, m, pre[i]);
}
}
int lastans = 0, x, y;
while(q--) {
read(x), read(y);
if(type) x ^= lastans, y ^= lastans;
printf("%d\n", lastans = (n - query(rt[x-1], rt[y], 0, m, 0, x-1)));
}
}