bzoj3514 Codechef MARCH14 GERALD07加強版 LCT&&主席樹

wulala

蔥娘說這是一個很巧妙的題。。

有一個比較獵奇的做法：首先把邊依次加到圖中，若目前這條邊與圖中的邊形成了環，那麼把這個環中最早加進來的邊彈出去

并将每條邊把哪條邊彈了出去記錄下來：ntr[i] = j，特别地，要是沒有彈出邊，ntr[i] = 0;

這個顯然是可以用LCT來弄的對吧。

然後對于每個詢問，我們的答案就是對l~r中ntr小于l的邊求和，并用n減去這個值

正确性可以YY一下：

如果一條邊的ntr >= l,那麼顯然他可以與從l ~ r中的邊形成環，那麼它對答案沒有貢獻

反之如果一條邊的ntr < l那麼它與從l ~ r中的邊是不能形成環的，那麼他對答案的貢獻為-1

對于查詢從l ~ r中有多少邊的ntr小于l，我反正是用的函數式線段樹

       我覺得這個已經講的很清楚了。

       然後發現自己最近做題自帶2倍常數。。（被STL卡了以後就一直這樣）。

AC代碼如下（以前LCT的模闆就是學(chao)黃學長的。。主席樹也是學(chao)黃學長的。。然後就看起來和黃學長一模一樣了o(╯□╰)o。。。23333）：

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 1000000000
#define N 400005
using namespace std;

int n,m,trtot,cnt,tp,ex[N],ey[N],stk[N],fa[N],c[N][2],pre[N],p[N],val[N];
int ls[N*10],rs[N*10],sum[N*10],rt[N];
bool rev[N];
int read(){
	int x=0; char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return x;
}
bool isrt(int x){
	return c[fa[x]][0]^x && c[fa[x]][1]^x;
}
int les(int x,int y){
	if (val[p[x]]<val[p[y]]) return p[x];
		else return p[y];
}
void maintain(int k){
	p[k]=k;
	p[k]=les(k,c[k][0]); p[k]=les(k,c[k][1]);
}
void rotate(int x){
	int y=fa[x],z=fa[y],l=(c[y][0]==x)?0:1,r=l^1;
	if (!isrt(y)){
		if (c[z][0]==y) c[z][0]=x; else c[z][1]=x;
	}
	fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
	c[y][l]=c[x][r]; c[x][r]=y;
	maintain(y); maintain(x);
}
void pushdown(int x){
	if (rev[x]){
		swap(c[x][0],c[x][1]);
		rev[x]=0; rev[c[x][0]]^=1; rev[c[x][1]]^=1;
	}
}
void splay(int x){
	stk[tp=1]=x; int i,y,z;
	for (i=x; !isrt(i); i=fa[i]) stk[++tp]=fa[i];
	while (tp) pushdown(stk[tp--]);
	while (!isrt(x)){
		y=fa[x]; z=fa[y];
		if (!isrt(y)){
			if (c[y][0]==x ^ c[z][0]==y) rotate(x);
				else rotate(y);
		}
		rotate(x);
	}
}
void access(int x){
	int y=0;
	for (; x; y=x,x=fa[x]){
		splay(x); c[x][1]=y; maintain(x);
	}
}
void makert(int x){
	access(x); splay(x); rev[x]^=1;
}
void link(int x,int y){
	makert(x); fa[x]=y;
}
void cut(int x,int y){
	makert(x); access(y); splay(y);
	c[y][0]=fa[x]=0;
}
int getanc(int x){
	access(x); splay(x);
	while (c[x][0]) x=c[x][0]; return x;
}
int getmin(int x,int y){
	makert(x); access(y); splay(y);
	return p[y];
}
void ins(int l,int r,int x,int &y,int v){
	y=++trtot; sum[y]=sum[x]+1;
	if (l==r) return; int mid=(l+r)>>1;
	if (v<=mid){ rs[y]=rs[x]; ins(l,mid,ls[x],ls[y],v); }
	else{ ls[y]=ls[x]; ins(mid+1,r,rs[x],rs[y],v); }
}
int qry(int x,int y,int l,int r,int v){
	if (r==v) return sum[y]-sum[x]; int mid=(l+r)>>1;
	if (v<=mid) return qry(ls[x],ls[y],l,mid,v);
	else return sum[ls[y]]-sum[ls[x]]+qry(rs[x],rs[y],mid+1,r,v);
}
int main(){
	n=read(); m=read(); int cas=read(),k=read(),i;
	for (i=0; i<=n; i++) val[p[i]=i]=inf; cnt=n;
	for (i=1; i<=m; i++){
		int x=read(),y=read(); ex[i]=x; ey[i]=y;
		if (x==y){ pre[i]=i; continue; }
		if (getanc(x)==getanc(y)){
			int z=getmin(x,y); pre[i]=val[z];
			cut(ex[pre[i]],z); cut(ey[pre[i]],z);
		}
		val[++cnt]=i; p[cnt]=cnt;
		link(x,cnt); link(y,cnt);
	}
	for (i=1; i<=m; i++) ins(0,m,rt[i-1],rt[i],pre[i]);
	int ans=0;
	while (cas--){
		int u=read(),v=read();
		if (k){ u^=ans; v^=ans; }
		printf("%d\n",ans=n-qry(rt[u-1],rt[v],0,m,u-1));
	}
	return 0;
}
           

by lych

2016.2.27