http://www.lydsy.com/JudgeOnline/problem.php?id=3514 (题目链接)
题意
给出$n$个点$m$条边的无向图，询问保留图中编号在$[l,r]$的边的时候图中的连通块的个数。
Solution
将边的编号作为权值用LCT维护一个最大生成树，同时记录一下加入当前边$i$会把哪一条原本在生成树中的边踢掉，记作$ntr[i]$。如果不会踢掉任意一条边，那么$ntr[i]=0$。如果$i$是自环，那么$ntr[i]=i$。
求出$ntr$数组有什么用呢，我们以它构建一棵主席树。对于一个询问$[l,r]$，我们想知道在这些边中有用的边有几条，那么有用的边$ntr$的前一条边的编号一定是在$l$之前的，所以我们在主席树上查询一下区间$[l,r]$中$ntr$在$[0,l-1]$中的边有几条。这样查出来的值就是有用的边的条数，每加入一条有用的边，都会时连通块个数-1，于是我们就可以统计答案了。
细节
cut的时候cut的是被ntr的边两端的节点，手一快就打错了，还查了好久T_T
代码
// bzoj3514
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define lim 1000000000
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int maxn=200010;
int n,m,Q,T,ans,rt[maxn],ntr[maxn];
struct edge {int u,v;}e[maxn];
struct node {
int son[2],s,rev;
int& operator [] (int x) {return son[x];}
};
namespace LCT {
int fa[maxn<<1];
node tr[maxn<<1];
void reverse(int x) {
tr[x].rev^=1;
swap(tr[x][0],tr[x][1]);
}
void pushup(int x) {
tr[x].s=x<=n ? inf : x;
int l=tr[x][0],r=tr[x][1];
if (l) tr[x].s=min(tr[x].s,tr[l].s);
if (r) tr[x].s=min(tr[x].s,tr[r].s);
}
void pushdown(int x) {
if (tr[fa[x]][0]==x || tr[fa[x]][1]==x) pushdown(fa[x]);
if (tr[x].rev) {
if (tr[x][0]) reverse(tr[x][0]);
if (tr[x][1]) reverse(tr[x][1]);
tr[x].rev^=1;
}
}
void rotate(int x) {
int y=fa[x],z=fa[y],l,r;
l=tr[y][1]==x;r=l^1;
if (tr[z][0]==y || tr[z][1]==y) tr[z][tr[z][1]==y]=x;
fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
tr[y][l]=tr[x][r];tr[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x) {
pushdown(x);
while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) {
int y=fa[x],z=fa[y];
if (tr[z][0]==y || tr[z][1]==y) {
if (tr[z][0]==y ^ tr[y][0]==x) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x) {
for (int y=0;x;y=x,x=fa[x])
splay(x),tr[x][1]=y,pushup(x);
}
void makeroot(int x) {
access(x);splay(x);reverse(x);
}
int query(int x,int y) {
makeroot(x);access(y);splay(y);return tr[y].s;
}
void link(int x,int y) {
makeroot(x);fa[x]=y;
}
void cut(int x,int y) {
makeroot(x);access(y);splay(y);
fa[x]=tr[y][0]=0;pushup(y);
}
int find(int x) {
return fa[x] ? find(fa[x]) : x;
}
void main() {
for (int i=1;i<=m;i++) {
scanf("%d%d",&e[i].u,&e[i].v);
if (e[i].u==e[i].v) ntr[i]=i;
else if (find(e[i].u)==find(e[i].v)) {
int x=query(e[i].u,e[i].v);
ntr[i]=x-n;
cut(x,e[x-n].u);
cut(x,e[x-n].v);
link(i+n,e[i].u);link(i+n,e[i].v);
}
else ntr[i]=0,link(i+n,e[i].u),link(i+n,e[i].v);
}
}
}
namespace Chairtree {
int sz;
node tr[maxn*40];
void build(int &u,int v,int l,int r,int val) {
if (!u) u=++sz;
if (l==r) {tr[u].s=tr[v].s+1;return;}
int mid=(l+r)>>1;
if (val<=mid) build(tr[u][0],tr[v][0],l,mid,val),tr[u][1]=tr[v][1];
else build(tr[u][1],tr[v][1],mid+1,r,val),tr[u][0]=tr[v][0];
tr[u].s=tr[tr[u][0]].s+tr[tr[u][1]].s;
}
int query(int u,int v,int l,int r,int ql,int qr) {
if (!u && !v) return 0;
if (l==ql && r==qr) return tr[v].s-tr[u].s;
int mid=(l+r)>>1;
if (qr<=mid) return query(tr[u][0],tr[v][0],l,mid,ql,qr);
else if (ql>mid) return query(tr[u][1],tr[v][1],mid+1,r,ql,qr);
else return query(tr[u][0],tr[v][0],l,mid,ql,mid)+query(tr[u][1],tr[v][1],mid+1,r,mid+1,qr);
}
}
using namespace Chairtree;
int main() {
scanf("%d%d%d%d",&n,&m,&Q,&T);
LCT::main();
for (int i=1;i<=m;i++) build(rt[i],rt[i-1],0,m,ntr[i]);
for (int l,r,i=1;i<=Q;i++) {
scanf("%d%d",&l,&r);
if (T) l^=ans,r^=ans;
ans=n-query(rt[l-1],rt[r],0,m,0,l-1);
printf("%d
",ans);
}
return 0;
}