Description：

$N$ 个点 $M$ 条边的无向图，询问保留图中编号在 $[l,r]$ 的边的时候图中的联通块个数。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

首先一条边如果连接了两个没连起来的点，那么联通块个数减一，如果形成了一个环，那么除去环上最小的边，只考虑剩下的边的话联通块个数还是减一，直接说做法，用一个 $LCT$ 维护动态生成树链上最小值，每次对于新加的一条边，如果两边没有联通，那么对于所有 $L\in[1,i]$ 联通块个数减一，如果已经联通了，找到权值最小的边 $p$ ，对于所有 $L\in[p+1,i]$ 联通块个数减一，于是就可以用主席树 $+$ 标记永久化来预处理出所有答案，第 $i$ 棵主席树第 $j$ 个位置维护的是 $L=j,R=i$ 的答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 200010

#define INF 0x3f3f3f3f

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,q,w;

namespace LCT

{

	struct node

	{

		int c[2],fa,pos;

		bool rev;

		node(){pos = INF;}

	}t[MAXN << 1];

	inline bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

	inline int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

	inline void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

	inline void maintain(int k)

	{

		if(k > n)t[k].pos = k;

		else t[k].pos = INF;

		if(t[k].c[0] != 0 && t[t[k].c[0]].pos < t[k].pos)t[k].pos = t[t[k].c[0]].pos;

		if(t[k].c[1] != 0 && t[t[k].c[1]].pos < t[k].pos)t[k].pos = t[t[k].c[1]].pos;

		return;

	}

	inline void rotate(int x)

	{

		register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

		if(!isroot(y))t[z].c[fy] = x;

		t[x].fa = z;

		connect(t[x].c[fx ^ 1],y,fx);

		connect(y,x,fx ^ 1);

		maintain(y);maintain(x);

		return;

	}

	inline void pushdown(int k)

	{

		if(t[k].rev)

		{

			t[t[k].c[0]].rev ^= 1;t[t[k].c[1]].rev ^= 1;

			swap(t[k].c[0],t[k].c[1]);t[k].rev = false;

		}

		return;

	}

	stack<int> s;

	inline void splay(int x)

	{

		s.push(x);

		for(register int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

		while(!s.empty()){pushdown(s.top());s.pop();}

		while(!isroot(x))

		{

			register int y = t[x].fa;

			if(isroot(y)){rotate(x);break;}

			if(id(x) == id(y)){rotate(y);rotate(x);}

			else{rotate(x);rotate(x);}

		}

		return;

	}

	inline void access(int k){for(register int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

	inline int findroot(int k){access(k);splay(k);while(t[k].c[0] != 0)k = t[k].c[0];return k;}

	inline void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

	inline void link(int x,int y){makeroot(x);t[x].fa = y;return;}

	inline void split(int x,int y){makeroot(x);access(y);splay(y);return;}

	inline void cut(int x,int y){split(x,y);t[x].fa = t[y].c[0] = 0;maintain(y);return;}

}

namespace PT

{

	struct node

	{

		int lc,rc;

		int tag;

		node(){tag = 0;}

	}t[MAXN * 60];

	int ptr = 0;

	inline int newnode(){return ++ptr;}

	int root[MAXN];

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void add(int &rt,int L,int R,int l,int r)

	{

		register int k = newnode();t[k] = t[rt];rt = k;

		if(L <= l && r <= R)

		{

			++t[rt].tag;

			return;

		}

		if(L <= mid)add(t[rt].lc,L,R,l,mid);

		if(R > mid)add(t[rt].rc,L,R,mid + 1,r);

		return;

	}

	int query(int rt,int p,int l,int r)

	{

		if(l == r)return t[rt].tag;

		register int res = 0;

		if(p <= mid)res = query(t[rt].lc,p,l,mid);

		else res = query(t[rt].rc,p,mid + 1,r);

		res += t[rt].tag;

		return res;

	}

}

struct edges

{

	int u,v;

}e[MAXN];

int main()

{

	n = rd();m = rd();q = rd();w = rd();

	PT::build(PT::root[0],1,m);

	for(register int i = 1;i <= n;++i)LCT::t[i].pos = INF;

	for(register int i = 1;i <= m;++i)LCT::t[i + n].pos = i + n;

	register int x,y;

	for(int i = 1;i <= m;++i)

	{

		PT::root[i] = PT::root[i - 1];

		e[i].u = x = rd();e[i].v = y = rd();

		if(x == y)continue;

		if(LCT::findroot(x) != LCT::findroot(y))

		{

			LCT::link(x,i + n);LCT::link(y,i + n);

			PT::add(PT::root[i],1,i,1,m);

		}

		else

		{

			LCT::split(x,y);

			register int p = LCT::t[y].pos - n;

			PT::add(PT::root[i],p + 1,i,1,m);

			LCT::cut(p + n,e[p].u);LCT::cut(p + n,e[p].v);

			LCT::link(i + n,e[i].u);LCT::link(i + n,e[i].v);

		}

	}

	register int lastans = 0;

	for(register int i = 1;i <= q;++i)

	{

		x = rd();y = rd();

		x ^= (lastans * w);y ^= (lastans * w);

		lastans = n - PT::query(PT::root[y],x,1,m);

		printf("%d\n",lastans);

	}

	return 0;

}