把边的编号看成边权，维护每个状态对应的最大生成树，得到一个数组a[i],表示第i条边在这个过程中替换的是那条边，询问时看一下a[l,r]内啊有多少个小于l的算一下答案就好；代码参考：http://blog.csdn.net/thy_asdf/article/details/50518526

//lct不好处理边权，把一条边转成夹在两个点之间的点； #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=400010,maxt=10000010,inf=1e9;struct edg{    int u,v;}e[maxn];struct node{    int l,r,v;}tr[maxt];int n,m,k,tot,root[maxn],a[maxn],type,lastans;void insert(int t,int l,int r,int &x){    ++tot;tr[tot]=tr[x];x=tot;    ++tr[tot].v;    if(l==r)return;    int mid=l+r>>1;    if(t<=mid)insert(t,l,mid,tr[x].l);    else insert(t,mid+1,r,tr[x].r);}int qs(int x,int y,int l,int r,int L,int R){    if(r
          
           R||l>r)return 0; if(l>=L&&r<=R)return tr[y].v-tr[x].v; int mid=l+r>>1; return qs(tr[x].l,tr[y].l,l,mid,L,R)+qs(tr[x].r,tr[y].r,mid+1,r,L,R); }struct node2{ int ls,rs,fa,is_root;}tre[maxn];int siz[maxn],mins[maxn],val[maxn],cnt,rev[maxn];void update(int x){ mins[x]=x; if(val[mins[tre[x].ls]]
           
            >n>>m>>k>>type; val[0]=inf; for(int i=1;i<=n;++i)mins[i]=i,val[i]=inf; for(int i=1;i<=m;++i)scanf("%d%d",&e[i].u,&e[i].v); pre(); int l,r; for(int i=1;i<=k;++i){ scanf("%d%d",&l,&r); if(type)l^=lastans,r^=lastans; printf("%d\n",lastans=(n-qs(root[l-1],root[r],0,m,0,l-1))); } return 0;}