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)));
	}
}