Bzoj3514:Codechef MARCH14 GERALD07加强版:LCT+主席树

题目链接:3514:Codechef MARCH14 GERALD07加强版

考试考到的一道题，20分暴力滚粗QAQ

莫队能做，做法基本同Bzoj4358

我才不会告诉你那题我昨天写了……

荏弱没话QAQ

对于这道题的正解，真的是很巧妙

对于一个联通块，我们要保证他是联通的且没有环，只要保证他是一棵生成树

考虑我们顺次将边添加进图中，对于一条边他的两个端点u、v如果在并查集中fa[u]!=fa[v]那么我们就减少了一个联通块

现在我们要知道怎么维护这一信息

考虑在区间[L,R]中的一条边x，我们把它放在了{1,x-1]形成的图中，发现它形成了一个环

那么这条边我们肯定不能要。但是对于区间[L,R]中的边，很可能离开了这条边就会少一个联通块

所以我们要记录这条边加入原图中，如果形成环可以替换掉这条边两端点的路径中最早的边是哪条，设为p

如果p在L以前，说明x确实在[L,R]中有贡献

所以我们删掉p，加入x，更新这个图，删边加边还要询问最早边什么的用LCT，以下标为键值统计最小值就可以

为什么要删掉p而加入x？因为如果不删p不加入x如果以后的边还会形成环，可以替换的最早的边就是p，而如果此时x和这条边在一个询问集合中……嘿嘿嘿

下一步是怎么统计答案

我们已经处理处每条边可以替换的边，在区间[L,R]中的所有边，对于某一条它可以替换的边在L以前，答案就会减少1，这个已经讨论过

所以我们需要知道[L,R]中的边有多少条它可以替换的边在L以前，这个用主席树来做

那么这道题就结束了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=400010;
const int inf=0x7fffffff/3;
int n,m,Q,sta[maxn],a[maxn],flag;
struct edge{int u,v;}e[maxn];
int lson[maxn*19],rson[maxn*19],c[maxn*19],T[maxn];

struct Nodes{
	int fa,c[2],rev,mi,v;
};
struct link_cut_tree{
	Nodes t[maxn]; int ToT;
	bool isroot(int x){return t[t[x].fa].c[0]!=x&&t[t[x].fa].c[1]!=x;}
	void init(){
		t[0].v=inf;
		for (int i=1;i<=n;++i) t[i].mi=i,t[i].v=inf;
	}
	void push_up(int x){
		t[x].mi=x;
		if (t[t[t[x].c[0]].mi].v<t[t[x].mi].v) t[x].mi=t[t[x].c[0]].mi;
		if (t[t[t[x].c[1]].mi].v<t[t[x].mi].v) t[x].mi=t[t[x].c[1]].mi;
	}
    void push_down(int x){
		if (t[x].rev){
			swap(t[x].c[0],t[x].c[1]);
			t[t[x].c[0]].rev^=1;
			t[t[x].c[1]].rev^=1; t[x].rev=0;
		}
    }
    void pre(int x){
		int top=0;
		for (;x;x=t[x].fa) sta[++top]=x;
		while (top) push_down(sta[top--]);
    }
    void rotate(int p,int x){
        int mark= p==t[x].c[1];
        int y=t[p].c[mark^1],z=t[x].fa;
        if (x==t[z].c[0]) t[z].c[0]=p;
        else if (x==t[z].c[1]) t[z].c[1]=p;
        if (y) t[y].fa=x; t[x].fa=p; t[x].c[mark]=y;
        t[p].c[mark^1]=x; t[p].fa=z; push_up(x);
    }
    void splay(int p){
        pre(p);
        while (!isroot(p)){
            int x=t[p].fa,y=t[x].fa;
            if (isroot(x)) rotate(p,x);
            else if (p==t[x].c[0]^x==t[y].c[0]) rotate(p,x),rotate(p,y);
            else rotate(x,y),rotate(p,x);
        }push_up(p);
    }
    void access(int x){
        for (int v=0;x;x=t[x].fa){
            splay(x); t[x].c[1]=v;
            t[v].fa=x; v=x;
        }
    }
    void rever(int x){
        access(x); splay(x); t[x].rev^=1;
    }
    void cut(int x,int y){
        rever(x); access(y); splay(y); t[y].c[0]=t[x].fa=0;
    }
    void link(int x,int y){
        rever(x); t[x].fa=y;
    }
    int find(int x){
        access(x); splay(x);
        while (t[x].c[0]) x=t[x].c[0];
        return x;
    }
    int query(int x,int y){
		rever(x); access(y); splay(y);
		return t[y].mi;
    }
    void getA(){
		ToT=n;
		for (int i=1;i<=m;++i){
			int u=e[i].u,v=e[i].v;
			if (u==v){a[i]=i;continue;}
			if (find(u)==find(v)){
				int x=query(u,v),y=t[x].v;
				a[i]=y; cut(e[y].u,x); cut(e[y].v,x);
			}++ToT; t[ToT].mi=ToT; t[ToT].v=i;
			link(u,ToT); link(v,ToT);
		}
    }
}lct;
int tot=1;
int update(int root,int pos,int val){
	if (!root) root=tot++,c[root]=0;
	int nr=tot++,tmp=nr,l=0,r=m;
	c[nr]=c[root]+val;
	while (l<r){
		int mid=(l+r)>>1;
		if (pos<=mid){
			lson[nr]=tot++;rson[nr]=rson[root];
			r=mid;root=lson[root];nr=lson[nr];
		}else if (pos>mid){
			lson[nr]=lson[root];rson[nr]=tot++;
			l=mid+1;root=rson[root];nr=rson[nr];
		}c[nr]=c[root]+val;
	}return tmp;
}

int query(int lr,int rr,int l,int r,int L,int R){
	if (l==L&&R==r) return c[rr]-c[lr];
	int mid=(l+r)>>1;
	if (R<=mid) return query(lson[lr],lson[rr],l,mid,L,R);
	else if (L>mid) return query(rson[lr],rson[rr],mid+1,r,L,R);
	else return query(lson[lr],lson[rr],l,mid,L,mid)+
	            query(rson[lr],rson[rr],mid+1,r,mid+1,R);
}

int main(){
	scanf("%d%d%d%d",&n,&m,&Q,&flag);
	for (int i=1;i<=m;++i)scanf("%d%d",&e[i].u,&e[i].v);
	lct.init(); lct.getA(); int lastans=0;
	for (int i=1;i<=m;++i) T[i]=update(T[i-1],a[i],1);
	for (int i=1;i<=Q;++i){
		int x,y; scanf("%d%d",&x,&y);
		if (flag) x^=lastans,y^=lastans;
		printf("%d\n",lastans=(n-query(T[x-1],T[y],0,m,0,x-1)));
	}
}