题目大意：

给定n个点m条边的无向图。求问当图中仅仅有【编号在[l,r]区间内】的边存在时图中的联通块个数 强制在线

注意联通块是指联通了就是同一块，不是Tarjan求的那种块

看到这题的那一刻我就想小便有木有0.0 这尼玛怎么做？可持久化并查集？ 暴力？ 分块乱搞？ 。。。

后来看了HZWER大神的博客才知道这样的巧妙的算法0.0 太强大了

直接复制wulala的题解 讲得非常清楚 不累述了

wulala

葱娘说这是一个非常巧妙的题。。

有一个比較猎奇的做法：首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去

并将每条边把哪条边弹了出去记录下来：ntr[i] = j，特别地，要是没有弹出边，ntr[i] = 0;

这个显然是能够用LCT来弄的对吧。

然后对于每一个询问，我们的答案就是对l~r中ntr小于l的边求和，并用n减去这个值

正确性能够YY一下：

假设一条边的ntr >= l,那么显然他能够与从l ~ r中的边形成环，那么它对答案没有贡献

反之假设一条边的ntr < l那么它与从l ~ r中的边是不能形成环的。那么他对答案的贡献为-1

对于查询从l ~ r中有多少边的ntr小于l，我反正是用的函数式线段树

这个真是太强大了0.0 假设这条边踢掉的最早的边也在[l,r]区间内 那么增加这条边一定对图的连通性没有影响 否则就会连接两个联通块 导致ans--

至于求l~r中有多少边的ntr小于l我用的是划分树 蒟蒻不会写主席树肿莫破。。

。

ntr。寝取り，果然是个够劲的名字。

。

。 于是为了保持这样的美好的意境我也牺牲了划分树中的a数组改成了ntr。。

。

把这个美好的意境传承下去吧。。

。

另外这题有自环 自环的话相当于自己ntr自己 直接记录ntr之后就返回好了

#include
     
      #include
      
       #include
       
        #include
        
         #define M 200200#define INF 2147483647using namespace std;struct edges{	int x,y;}e[M];struct abcd{	abcd *fa,*ls,*rs;	int num,minnum;	bool rev_mark;	abcd(int x);	void Reverse();	void Push_Up();	void Push_Down();}*null=new abcd(INF),*tree[M<<1];abcd :: abcd(int x){	fa=ls=rs=null;	num=minnum=x;	rev_mark=0;}void abcd :: Reverse(){	rev_mark^=1;	swap(ls,rs);}void abcd :: Push_Up(){	minnum=min(ls->minnum,rs->minnum);	minnum=min(minnum,num);}void abcd :: Push_Down(){	if(fa->ls==this||fa->rs==this)		fa->Push_Down();	if(rev_mark)	{		ls->Reverse();		rs->Reverse();		rev_mark=0;	}}void Zig(abcd *x){	abcd *y=x->fa;	y->ls=x->rs;	x->rs->fa=y;	x->rs=y;	x->fa=y->fa;	if(y==y->fa->ls)		y->fa->ls=x;	else if(y==y->fa->rs)		y->fa->rs=x;	y->fa=x;	y->Push_Up();}void Zag(abcd *x){	abcd *y=x->fa;	y->rs=x->ls;	x->ls->fa=y;	x->ls=y;	x->fa=y->fa;	if(y==y->fa->ls)		y->fa->ls=x;	else if(y==y->fa->rs)		y->fa->rs=x;	y->fa=x;	y->Push_Up();}void Splay(abcd *x){	x->Push_Down();	while(x->fa->ls==x||x->fa->rs==x)	{		abcd *y=x->fa,*z=y->fa;		if(x==y->ls)		{			if(y==z->ls)				Zig(y);			Zig(x);		}		else		{			if(y==z->rs)				Zag(y);			Zag(x);		}	}	x->Push_Up();}void Access(abcd *x){	abcd *y=null;	while(x!=null)	{		Splay(x);		x->rs=y;		x->Push_Up();		y=x;		x=x->fa;	}}abcd* Find_Root(abcd *x){	while(x->fa!=null)		x=x->fa;	return x;}void Move_To_Root(abcd *x){	Access(x);	Splay(x);	x->Reverse();}void Link(abcd *x,abcd *y){	Move_To_Root(x);	x->fa=y;}void Cut(abcd *x,abcd *y){	Move_To_Root(x);	Access(y);	Splay(y);	x->fa=null;	y->ls=null;	y->Push_Up();}int Query(abcd *x,abcd *y){	Move_To_Root(x);	Access(y);	Splay(y);	return y->minnum;}int n,m,q,type,ans;int ntr[M],b[M],c[M],s[20][M];void Insert(int p){	if(e[p].x==e[p].y)	{		ntr[p]=p;		return ;	}	abcd *x=tree[e[p].x],*y=tree[e[p].y];	if( Find_Root(x)==Find_Root(y) )	{		int temp=Query(x,y);		ntr[p]=temp;		Cut(tree[n+temp],tree[e[temp].x]);		Cut(tree[n+temp],tree[e[temp].y]);		free(tree[n+temp]);	}	tree[n+p]=new abcd(p);	Link(tree[n+p],tree[e[p].x]);	Link(tree[n+p],tree[e[p].y]);}void Build_Tree(int l,int r,int dpt){	int i,mid=l+r>>1;	int l1=l,l2=mid+1;	int left=mid-l+1;	if(l==r)		return ;	for(i=l;i<=r;i++)		left-=(ntr[i]
         
          >1;	int l1=(x==l?0:s[dpt][x-1]),l2=s[dpt][y];	if(x>y)		return 0;	if(l==r)		return ntr[mid]
          
           >n>>m>>q>>type; for(i=1;i<=n;i++) tree[i]=new abcd(INF); for(i=1;i<=m;i++) scanf("%d%d",&e[i].x,&e[i].y),Insert(i); memcpy(c+1,ntr+1,sizeof(c[0])*m); sort(c+1,c+m+1); Build_Tree(1,m,0); for(i=1;i<=q;i++) { scanf("%d%d",&x,&y); x^=ans*type;y^=ans*type; ans=n-Get_Ans(1,m,0,x,y,x); printf("%d\n", ans ); }}