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

第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。
接下来M行，代表图中的每条边。
接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

K行每行一个整数代表该组询问的联通块个数。

对于100%的数据，1≤N、M、K≤200,000。

2016.2.26提高时限至60s

By zhonghaoxi

#include <cstdio>inline int nextChar(void) {  static const int siz = 1 << 20;  static char buf[siz];  static char *hd = buf + siz;  static char *tl = buf + siz;  if (hd == tl)    fread(hd = buf, 1, siz, stdin);  return int(*hd++);}inline int nextInt(void) {  register int ret = 0;  register int neg = false;  register int bit = nextChar();  for (; bit < 48; bit = nextChar())    if (bit == ‘-‘)neg ^= true;  for (; bit > 47; bit = nextChar())    ret = ret * 10 + bit - ‘0‘;  return neg ? -ret : ret;}template <class T>inline void Swap(T &a, T &b) {  T c;  c = a;  a = b;  b = c;}template <class T>inline T Max(const T &a, const T &b) {  return a > b ? a : b;}template <class T>inline T Min(const T &a, const T &b) {  return a < b ? a : b;}const int mxn = 400005;const int inf = 1000000007;int n, m, q, e, ntr[mxn];struct edge {  int x, y;}E[mxn];namespace LCT {  int top = 0;  int stk[mxn];  int val[mxn];  int rev[mxn];  int min[mxn];  int fat[mxn];  int son[mxn][2];  inline bool isroot(int t) {    int f = fat[t];    if (!f)return true;    if (son[f][0] == t)return false;    if (son[f][1] == t)return false;    return true;  }  inline void update(int t) {    min[t] = val[t];    if (son[t][0])min[t] = Min(min[t], min[son[t][0]]);    if (son[t][1])min[t] = Min(min[t], min[son[t][1]]);  }  inline void push(int t) {    rev[t] = 0;    Swap(son[t][0], son[t][1]);    if (son[t][0])rev[son[t][0]] ^= 1;    if (son[t][1])rev[son[t][1]] ^= 1;  }  inline void pushdown(int t) {    for (stk[++top] = t; t; )      stk[++top] = t = fat[t];    for (; top; --top)      if (rev[stk[top]])      	push(stk[top]);  }  inline void connect(int t, int f, int s) {    if (t)fat[t] = f;    if (f)son[f][s] = t;  }  inline void rotate(int t) {    int f = fat[t];    int g = fat[f];    int s = son[f][1] == t;    connect(son[t][!s], f, s);    connect(f, t, !s);    fat[t] = g;    if (g && son[g][0] == f)son[g][0] = t;    if (g && son[g][1] == f)son[g][1] = t;    update(f);    update(t);  }  inline void splay(int t) {    pushdown(t);    while (!isroot(t)) {      int f = fat[t];      int g = fat[f];      if (isroot(f))	      rotate(t);      else {	      int a = f && son[f][1] == t;	      int b = g && son[g][1] == f;	      if (a == b)	        rotate(f), rotate(t);	      else	        rotate(t), rotate(t);      }    }  }  inline void access(int t) {    for (int p = 0; t; p = t, t = fat[t])      splay(t), son[t][1] = p, update(t);  }  inline void makeroot(int t) {    access(t), splay(t), rev[t] ^= 1;  }  inline int find(int t) {    access(t), splay(t);    while (son[t][0])      t = son[t][0];    return t;  }  inline void link(int t, int f) {    makeroot(t), fat[t] = f;  }  inline void cut(int a, int b) {    makeroot(a), access(b), splay(b);    if (son[b][0] == a)      son[b][0] = fat[a] = 0, update(b);  }  inline void preworkNTR(void) {    for (int i = 1; i <= n; ++i)      val[i] = min[i] = inf;    for (int i = 1; i <= m; ++i) {      if (E[i].x == E[i].y) {        ntr[i] = m;        continue;      }      if (find(E[i].x) == find(E[i].y)) {	      makeroot(E[i].x);	      access(E[i].y);	      splay(E[i].y);	      ntr[i] = min[E[i].y];	      cut(E[ntr[i]].x, ntr[i] + n);	      cut(E[ntr[i]].y, ntr[i] + n);      }      val[i + n] = min[i + n] = i;      link(E[i].x, i + n);      link(E[i].y, i + n);    }  }}namespace CMT {  const int K = 25;  int tot = 0;  int sum[K * mxn];  int lsn[K * mxn];  int rsn[K * mxn];  int rot[K * mxn];  void insert(int &t, int p, int l, int r, int v) {    t = ++tot;    lsn[t] = lsn[p];    rsn[t] = rsn[p];    sum[t] = sum[p] + 1;    if (l == r)return;    int mid = (l + r) >> 1;    if (v <= mid)      insert(lsn[t], lsn[p], l, mid, v);    else      insert(rsn[t], rsn[p], mid + 1, r, v);  }  int query(int t, int l, int r, int x, int y) {    if (!t)return 0;    if (l == x && r == y)      return sum[t];    int mid = (l + r) >> 1;    if (y <= mid)      return query(lsn[t], l, mid, x, y);    else if (x > mid)      return query(rsn[t], mid + 1, r, x, y);    else      return query(lsn[t], l, mid, x, mid) + query(rsn[t], mid + 1, r, mid + 1, y);  }    inline void preworkNTR(void) {    for (int i = 1; i <= m; ++i)      insert(rot[i], rot[i - 1], 0, m, ntr[i]);  }  inline int solve(int l, int r) {    return n - query(rot[r], 0, m, 0, l - 1) + query(rot[l - 1], 0, m, 0, l - 1);  }}signed main(void) {  n = nextInt();  m = nextInt();  q = nextInt();  e = nextInt();  for (int i = 1; i <= m; ++i)    E[i].x = nextInt(),    E[i].y = nextInt();  LCT::preworkNTR();   CMT::preworkNTR();  int lastans = 0;  for (int i = 1; i <= q; ++i) {    int L = nextInt();    int R = nextInt();    if (e)      L ^= lastans,      R ^= lastans;    printf("%d\n", lastans = CMT::solve(L, R));  }}