天天看點

線段樹分治總結(線段樹分治,線段樹,并查集,樹的dfn序,二分圖染色)

閑話

stO貓锟學長,滿腦子神仙DS

網上有不少Dalao把線段樹分治也歸入CDQ分治?

還是聽聽YCB巨佬的介紹:

狹義:隻計算左邊對右邊的貢獻。
廣義:隻計算外部對内部的貢獻。
           

看來可以了解為廣義下的。

不過叫它線段樹分治挺形象的啊!

線段樹分治思想

我們在做CDQ的時候,将詢問和操作通通視為元素,在歸并過程中統計左邊的操作對右邊的詢問的貢獻。

而線上段樹分治中,詢問被固定了。按時間軸确定好詢問的序列以後,我們還需要所有的操作都會影響一個時間區間。而這個區間,毫無疑問正好對應着詢問的一段區間。

于是,我們可以将每一個操作丢到若幹詢問裡做區間修改了,而線段樹可以高效地維護。我們開一個葉子節點下标為詢問排列的線段樹,作為分治過程的底層結構。

具體的實作,仍然要看題目。

例題1

BZOJ4025二分圖(點選進入題目)

首先,圖是二分圖的充要條件是不存在奇環。

這個性質非常好。我們可以維護一棵生成樹,假如目前要加入一條邊\(x-y\),而生成樹中\(x\)到\(y\)的路徑上有偶數條邊,那麼就會形成奇環。如果\(x\)到\(y\)的路徑上有奇數條邊,就沒問題,而且去掉這條邊不會影響後續奇偶性的判斷。這就讓我們想到LCT做法:像WC2005雙面棋盤一樣,維護關于邊删除時間的最大生成樹,每次加邊并判斷。這裡不詳細展開。

關于維護奇偶性,我們還可以這樣想:二分圖染色!每次新加入一條邊的時候,我們需要保證\(x,y\)之前其中之一未被染色或已染上不同顔色。是以我們參考NOIP2010關押罪犯,維護并查集,對每個點\(x\)額外建一個點\(x'\)表示它的反集,在加邊時,如果\(x,y\)位于同一集合,将不再是二分圖。否則合并\(x,y'\)和\(y,x'\)。

但是邊有存在時間,而并查集顯然不能随意删邊。這時候,線段樹分治的一大妙用就派上用場了。

發現每個時刻都要詢問是否為二分圖,我們就對時間建立線段樹。對于每條邊,我們就按照區間加法的模式,把邊挂在出現時間對應線段樹内的\(\log\)個節點上,用連結清單實作。分治時,從根節點出發,每到一個節點,将挂在該節點上的所有邊合并,然後遞歸處理左兒子和右兒子。如果發現有某條邊合并會出現奇環,那麼顯然可以斷言,目前線段樹節點所對應的時間區間都不會形成二分圖。當成功到達葉子節點的時候,我們驚奇地發現,在這一時刻的所有邊已經在并查集中,而這一時刻也得到了

Yes

的肯定答案!

一口氣搞完了線段樹分治流程的一大半,現在我們看看之前不能随意删邊的問題。發現我們周遊線段樹過程的本質,實際上是跑了一遍dfn序。這明顯是一個棧的過程,不斷向下周遊,同時加邊;再進行回溯,我們要删去的是最後加的邊!而使用按秩合并不路徑壓縮的并查集,我們就可以輕松做到可撤銷最後一步的加邊。實作的時候,也要寫一個棧,儲存每次并查集合并的有關資訊(合并時加入的邊,合并後樹高\(dep\)的變化),線上段樹中處理完左右子樹後,将在目前節點加入的邊删除。

分治過程至此結束。來分析一下複雜度。每條邊會挂在\(\log T\)個線段樹節點上。因為并查集沒有路徑壓縮,是以每次加邊删邊判連通性時都需要跳\(\log n\)次\(fa\)。于是得出了總複雜度\(m\log n\log T\)。

寫法上,蒟蒻還通過許多Dalao的部落格了解到另一種用異或和維護奇偶性的并查集寫法。比起蒟蒻提到的這種,常數小了一半,但感覺思路沒那麼簡潔(其實是因為我這種弱雞弄不懂比不上Dalao)

實作細節方面,注意題目中時間段與時刻的差別(時間段從\(1\)開始,時刻從\(0\)開始)。資料中還有某些邊出現了“瞬閃”的現象(出現時刻等于消失時刻),做區間加法時不特判一下會RE。資料中還有自環(不能構成二分圖),不過使用蒟蒻這種并查集寫法似乎沒影響。

#include<cstdio>
#define I inline
#define RG register
#define R RG int
const int N=2e5,M=N<<1,L=4e6;
char buf[M],*pe=buf+M,*pp=pe-1;
int p,st[L],u[M],v[M],f[M],d[M],he[M],ne[L],id[L];
bool fl[L];
I void gc(){
	if(++pp==pe)fread(pp=buf,1,M,stdin);
}
I void pc(RG char C){
	if(++pp==pe)fwrite(pp=buf,1,M,stdout);*pp=C;
}
I int in(){
	gc();while(*pp<'-')gc();
	R x=*pp&15;gc();
	while(*pp>'-')x=x*10+(*pp&15),gc();
	return x;
}
I int get(R x){//直接跳fa
	while(f[x])x=f[x];
	return x;
}
I void merge(R x,R y){
	if(x==y)return;
	if(d[x]>d[y]){R t=x;x=y;y=t;}
	f[st[++p]=x]=y;//按秩合并,資訊壓入棧
	d[y]+=fl[p]=d[x]==d[y];//注意dep有沒有變也要壓
}
void upd(R t,R l,R r,R s,R e,R i){//區間加
	if(l==s&&r==e){
		ne[++p]=he[t];id[he[t]=p]=i;//挂鍊
		return;
	}
	R m=(l+r)>>1;
	if(e<=m)upd(t<<1,l,m,s,e,i);
	else if(s>m)upd(t<<1|1,m+1,r,s,e,i);
	else upd(t<<1,l,m,s,m,i),upd(t<<1|1,m+1,r,m+1,e,i);
}
void div(R t,R l,R r){
	R x,y,i,m=(l+r)>>1,lst=p;
	for(i=he[t];i;i=ne[i]){
		if((x=get(u[id[i]]))==(y=get(v[id[i]]))){
			for(;l<=r;++l)pc('N'),pc('o'),pc('\n');
			goto E;//出現奇環,斷定整個區間不合法
		}
		merge(get(u[id[i]]+N),y);//合并反點
		merge(get(v[id[i]]+N),x);
	}
	if(l==r)pc('Y'),pc('e'),pc('s'),pc('\n');
	else div(t<<1,l,m),div(t<<1|1,m+1,r);
  E:for(;p>lst;--p)//撤銷
		d[f[st[p]]]-=fl[p],f[st[p]]=0;
}
int main(){//g++:unused variable ‘n’。蒟蒻:叫我怎麼用你?
	R n=in(),m=in(),t=in(),s,e;
	for(R i=1;i<=m;++i){
		u[i]=in();v[i]=in();s=in();e=in();
		if(s!=e)upd(1,1,t,s+1,e,i);//特判
	}
	pp=buf-1;div(1,1,t);
	fwrite(buf,1,pp-buf+1,stdout);
	return 0;
}
           

例題二

BZOJ3237[Ahoi2013]連通圖(點選進入題目)

這一個就沒那麼裸了,并沒有展現任何詢問的時間軸,以及修改對應的時間區間。

可是,一個圖任意删邊我們還是沒法做,仍然要轉化成加邊。我們強行按照先後順序對詢問建時間軸,猛然發現,原來每條邊的存在仍然是若幹段時間區間!因為删邊意味着由一段時間區間分裂成兩段,是以總的段數控制在\(O(k)\)級别。

當然還是可以大力LCT。

當然接着使用線段樹分治。這裡的并查集使用帶權的,維護好目前連通塊大小。如果大小等于\(n\)說明圖連通。

其它的部分代碼幾乎照搬。當然由删邊的時間點轉化為加邊的時間區間需要寫一個連結清單實作,蒟蒻使用了STL的list(又是第一次學一個STL。。。)

複雜度仍然是兩個\(\log\),不過據說有随機權值的巧妙做法?

#include<cstdio>
#include<list>
#define I inline
#define RG register
#define R RG int
#define G c=getchar()
using namespace std;
const int N=2e5+9,M=4e5+9,L=8e6+9;
int n,p,st[M],f[N],s[N],d[N],a[M],b[M],he[M<<1],ne[L],id[L];
bool fl[M];
list<int>li[M];
I int in(){
	RG char G;
	while(c<'-')G;
	R x=c&15;G;
	while(c>'-')x*=10,x+=c&15,G;
	return x;
}
I int get(R x){
	while(f[x])x=f[x];
	return x;
}
void upd(R t,R l,R r,R s,R e,R i){
	if(l==s&&r==e){
		ne[++p]=he[t];id[he[t]=p]=i;
		return;
	}
	R m=(l+r)>>1;
	if(e<=m)upd(t<<1,l,m,s,e,i);
	else if(s>m)upd(t<<1|1,m+1,r,s,e,i);
	else upd(t<<1,l,m,s,m,i),upd(t<<1|1,m+1,r,m+1,e,i);
}
void div(R t,R l,R r){
	R i,x,y,m=(l+r)>>1,lst=p;
	for(i=he[t];i;i=ne[i]){
		if((x=get(a[id[i]]))==(y=get(b[id[i]])))continue;
		if(s[x]+s[y]==n){//剪枝,對複雜度并沒有什麼優化
			for(;l<=r;++l)puts("Connected");
			goto E;
		}
		if(d[x]>d[y])swap(x,y);
		s[f[st[++p]=x]=y]+=s[x];//帶權合并
		d[y]+=fl[p]=d[x]==d[y];
	}
	if(l==r)puts("Disconnected");
	else div(t<<1,l,m),div(t<<1|1,m+1,r);
  E:for(;p!=lst;--p)
		d[f[x=st[p]]]-=fl[p],s[f[x]]-=s[x],f[x]=0;
}
int main(){
	n=in();R m=in(),k,i,lst;
	RG list<int>::iterator it;
	for(i=1;i<=n;++i)s[i]=1;
	for(i=1;i<=m;++i)
		a[i]=in(),b[i]=in();
	k=in();
	for(i=1;i<=k;++i)
		for(R c=in();c;--c)
			li[in()].push_back(i);
	for(i=1;i<=m;++i){
		li[i].sort();li[i].push_back(k+1);//排個序
		for(lst=1,it=li[i].begin();it!=li[i].end();++it){
			if(lst!=*it)upd(1,1,k,lst,*it-1,i);
			lst=*it+1;//把區間弄出來
		}
	}
	p=0;div(1,1,k);
	return 0;
}