【雅礼联考GDOI2017模拟9.2】Ztxz16学图论

本文主要是介绍【雅礼联考GDOI2017模拟9.2】Ztxz16学图论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

众所周知，Zjr506是算法之神，因此Ztxz16经常向他请教算法。这一天，Zjr506在教导了Ztxz16关于图论方面的一些算法后，给他出了一道图论题作为家庭作业：
给定N个点，M条无向边，Q个询问，每个询问给定L, R，问连上第L~R条边后，图中有多少联通块（询问之间互不影响）。
Ztxz16智商太低，百思不得其解，只好向你请教这个问题。

Input

第一行输入N M Q
接下来M行每行两个整数代表一条边
接下来Q行每行两个整数代表一个询问

Output

输出Q行，代表这个询问中联通块的个数

Sample Input

3 3 3
1 2
2 3
1 3
1 1
2 3
1 3

Sample Output

2
1
1

Data Constraint

20%的数据保证N, M, Q <= 1000
60%的数据保证N, M, Q <= 50000
100%的数据保证N, M, Q <= 200000, L <= R

Solution

我们知道，如果有一颗N个节点的树，那么有n-1条边
那么随便思考一下就会发现，一共有n个点，有m条边，那么联通块的个数有n-m个

那么我们从后往前加边，当i号边加入时，有可能会使原来的树存在环，这时要找到环上编号最大的边（为什么？后面再说），把它去掉，维护的任然是树（森林）
这个操作可以用LCT解决
如果没有出现环，就将两棵树合并起来
这个用并查集做

怎么求答案呢？
对于所有询问的l=当前加入的边i的，需要知道l号边到r号边有多少条边在树（森林）中，然后用n-这个边数就是答案（第一段说的），这个用线段树或树状数组维护
那么为什么要删掉编号最大的边呢，很明显所有的l~r询问，如果l相同，r大的一定包括了r小的边，所以在LCT也就是维护的那个树（森林）中，尽量使用编号小的边

没了！？

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 501000
using namespace std;
int n,m,p[N],fa[N],c[N],c1[N],b[N],t[N][2],d[N],tree[N],rev[N],ans[N],qq,father[N];
struct node{int x,y,z;
}a[N],q[N];
bool cnt(node x,node y){return (x.x<y.x)||((x.x==y.x)&&(x.y<y.y));}
int lr(int x){return x==t[fa[x]][1];}
int gf(int x){return father[x]==0?x:father[x]=gf(father[x]);}
void updata(int x)
{int mx=c[t[x][0]],m2=c1[t[x][0]];if(c[t[x][1]]>mx) mx=c[t[x][1]],m2=c1[t[x][1]];if(b[x]>mx) mx=b[x],m2=x;c[x]=mx,c1[x]=m2;
}
void rotate(int x)
{int y=fa[x],k=lr(x);t[y][k]=t[x][1-k];if(t[x][1-k]) fa[t[x][1-k]]=y;fa[x]=fa[y];if(fa[y]) t[fa[y]][lr(y)]=x;else p[x]=p[y],p[y]=0;fa[y]=x;t[x][1-k]=y;updata(y);updata(x);
}
void down(int x)
{if(rev[x]==0) return;swap(t[x][0],t[x][1]);rev[t[x][0]]^=1;rev[t[x][1]]^=1;rev[x]=0;
}
void xc(int x,int y)
{do{d[++d[0]]=x;x=fa[x];}while(x!=y);for(;d[0];d[0]--) down(d[d[0]]);
}
void splay(int x,int y)
{xc(x,y);while(fa[x]!=y){if(fa[fa[x]]!=y)if(lr(x)==lr(fa[x])) rotate(fa[x]);else rotate(x);rotate(x);}
}
void access(int x)
{int y=0;while(x>0){splay(x,0);fa[t[x][1]]=0,p[t[x][1]]=x;t[x][1]=y,p[y]=0,fa[y]=x;updata(x);y=x;x=p[x];}
}
void makeroot(int x)
{access(x);splay(x,0);rev[x]^=1;
}
void link(int x,int y)
{makeroot(x);p[x]=y;
}
void cut(int x,int y)
{makeroot(x);access(y);splay(y,0);t[y][0]=0;fa[x]=p[x]=0;updata(y);
}
int find(int x,int y)
{makeroot(x);access(y);splay(x,0);splay(y,x);return c1[t[y][0]];
}
int lowbit(int x){return x&(-x);}
void insert(int x,int k)
{for(;x<=n;x+=lowbit(x)) tree[x]+=k;
}
int get(int x)
{int ans=0;for(;x;x-=lowbit(x)) ans+=tree[x];return ans;
}
int main()
{scanf("%d%d%d",&n,&m,&qq);fo(i,1,m) scanf("%d%d",&a[i].x,&a[i].y);fo(i,1,qq) scanf("%d%d",&q[i].x,&q[i].y),q[i].z=i;sort(q+1,q+qq+1,cnt);int r=qq;fd(i,m,1){if(a[i].x!=a[i].y){int x=gf(a[i].x),y=gf(a[i].y);if(x==y){int k=find(a[i].x,a[i].y)-n;cut(a[k].x,k+n),cut(k+n,a[k].y);insert(k,-1);b[i+n]=i;link(a[i].x,i+n),link(i+n,a[i].y);}else{b[i+n]=i;link(a[i].x,i+n),link(i+n,a[i].y);father[x]=y;}insert(i,1);    }for(;q[r].x==i;r--) ans[q[r].z]=n-get(q[r].y)+get(q[r].x-1);}fo(i,1,qq) printf("%d\n",ans[i]);
}