[ Lowest Common Ancestor , LCA Euler Tour Technique ] 最近共同祖先樹壓平轉RMQ算法

想法就是把樹壓平，然後紀錄當前節點u的深度在dep[u]，紀錄時間戳記，進入的時候要紀錄一次，出來的時候也要記錄，把當前點u進入的時間戳紀錄在in[u]中，時間戳的大小為2*n，所以必須用兩倍的記憶體來維護。之後就轉成RMQ問題
查詢a,b兩點的LCA=dep[in[a]]到dep[in[b]]中，最小深度的時間戳經過的那個點

	#define MAXN 100000
	typedef vector<int >::iterator VIT;
	int dep[MAXN+5],in[MAXN+5];
	int vs[2*MAXN+5];
	int cnt;/*時間戳*/
	vector<int >G[MAXN+5];
	void dfs(int x,int pa){
	in[x]=++cnt;
	vs[cnt]=x;
	for(VIT i=G[x].begin();i!=G[x].end();++i){
	if(*i==pa)continue;
	dep[*i]=dep[x]+1;
	dfs(*i,x);
	vs[++cnt]=x;
	}
	}

view raw Euler Tour Technique.cpp hosted with ❤ by GitHub

查詢:

	inline int find_lca(int a,int b){
	if(in[a]>in[b])swap(a,b);
	return RMQ(in[a],in[b]);
	}

view raw query.cpp hosted with ❤ by GitHub

RMQ的部分就要自己維護了，使用線段樹效能會非常差，在n,q<=100000的情況下使用稀疏表的效能與使用樹鏈剖分的效能差不多

[ Lowest Common Ancestor , LCA Doubling Search ] 最近共同祖先倍增演算法

首先建立一張倍增表，pa[i][x]表示x的第$2^i$的祖先，若不存在則為$-1$，可以在DFS或BFS的過程中求得，複雜度為$\ord{N*MAX\_LOG}$

對於每筆詢問，我們可以利用剛剛求得的倍增表，在$\ord{MAX\_LOG}$的時間在線查詢
先將要查詢的a,b兩點較深的點移至較淺的點的深度，之後二分搜LCA的位置
附上模板:

	#define MAXN 100000
	#define MAX_LOG 17
	typedef vector<int >::iterator VIT;
	int pa[MAX_LOG+1][MAXN+5],dep[MAXN+5];
	vector<int >G[MAXN+5];
	void dfs(int x,int p){
	pa[0][x]=p;
	for(int i=0;i+1<MAX_LOG;++i){
	pa[i+1][x]=pa[i][pa[i][x]];
	}
	for(VIT i=G[x].begin();i!=G[x].end();++i){
	if(*i==p)continue;
	dep[*i]=dep[x]+1;
	dfs(*i,x);
	}
	}
	inline int find_lca(int a,int b){
	if(dep[a]>dep[b])swap(a,b);
	for(int i=dep[b]-dep[a],k=0;i;i/=2){
	if(i&1)b=pa[k][b];
	++k;
	}
	if(a==b)return a;
	for(int i=MAX_LOG;i>=0;--i){
	if(pa[i][a]!=pa[i][b]){
	a=pa[i][a];
	b=pa[i][b];
	}
	}
	return pa[0][a];
	}

view raw Doubling Search.cpp hosted with ❤ by GitHub

[ Lowest Common Ancestor , LCA Tarjan's Algorithm ] 最近共同祖先tarjan演算法

tarjan算法的步驟是(當dfs到節點u時):

在並查集中建立僅有u的集合,設置該集合的祖先為u
對u的每個孩子v:

1. 遞迴處理v
2. 合併v的集合到父節點u的集合,確保集合的祖先是u

設置u為已遍歷
處理關於u的查詢,若查詢(u,x)中的x已遍歷過,則LCA(u,x) = x所在的集合的祖先

因為只進行過一次DFS，所以複雜度為$\ord{(N+Q)*\alpha(N)}$，為了優化並查集，這裡採用啟發式合併，因此為了記錄集合的祖先而外增加了一個數組head
其雖為線性，但是效率並不怎麼好，跟倍增法的效能差不多

	#define MAXN 100000
	#define MAXQ 100000
	typedef vector<int >::iterator VIT;
	typedef vector<pair<int,int> >::iterator VPIT;
	int tr[MAXN+5],siz[MAXN+5];/*並查集，dfs前必須初始化*/
	int head[MAXN+5],ans[MAXQ+5];
	bool v[MAXN+5];/*走訪標記*/
	vector<int >G[MAXN+5];
	vector<pair<int,int> >Q[MAXN+5];
	inline void init(int n){/*初始化並查集*/
	for(int i=1;i<=n;++i){
	tr[i]=i;
	siz[i]=1;
	}
	}
	int find(int x){
	return tr[x]==x?x:tr[x]=find(tr[x]);
	}
	inline void merge(int a,int b){
	a=find(a);
	b=find(b);
	if(a==b)return;
	if(siz[a]<siz[b])swap(a,b);
	tr[b]=a;
	siz[a]+=siz[b];
	}
	void dfs(int u,int pa){
	head[u]=u;
	for(VIT i=G[u].begin();i!=G[u].end();++i){
	if(*i==pa)continue;
	dfs(*i,u);
	merge(u,*i);
	head[find(u)]=u;/*記錄u所在集合的頭為u*/
	}
	v[u]=1;
	for(VPIT i=Q[u].begin();i!=Q[u].end();++i){
	if(v[i->first])ans[i->second]=head[find(i->first)];
	}
	}

view raw LCA Tarjan.cpp hosted with ❤ by GitHub

使用方法也很簡單，只需要將每個詢問的兩點記錄起來即可

	int n,m,a,b;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;++i){
	scanf("%d%d",&a,&b);
	G[a].push_back(b);
	G[b].push_back(a);
	}
	for(int i=0;i<m;++i){/*紀錄詢問*/
	scanf("%d%d",&a,&b);
	Q[a].push_back(make_pair(b,i));
	Q[b].push_back(make_pair(a,i));
	}
	init(n);
	dfs(1,-1);/*假設編號為1~n，root=1*/
	for(int i=0;i<m;++i)printf("%d\n",ans[i]);

view raw query.cpp hosted with ❤ by GitHub

[ Mo's algorithm ]莫隊算法

對於一些詢問區間答案的資料結構題，我們已經知道了區間[l,r]的答案，且能在極少的時間( $\ord 1$ or $\ord{logN}$ )內得到區間[l+1,r]、[l-1,r]、[l,r+1]、[l,r-1]的答案，題目也准許離線，只要滿足這些性質就可以使用莫隊。

首先我們須將所有詢問記錄下來，將序列分成sqrt(n)塊，找出每筆詢問l所在的塊，每塊內r由小排到大

	#define MAXQ 100000
	struct Q{
	int l,r,i,block;
	inline bool operator<(const Q &b)const{
	return block==b.block?r<b.r:block<b.block;
	}
	}q[MAXQ+5];

view raw struct.cpp hosted with ❤ by GitHub

	lim=1+(int)sqrt(n);
	for(int i=0;i<m;++i){
	scanf("%d%d",&q[i].l,&q[i].r);
	q[i].block=q[i].l/lim;
	q[i].i=i;
	}
	sort(q,q+m);

view raw scanf query.cpp hosted with ❤ by GitHub

這裡n是序列的長度

之後就按造順序一個一個將序列元素在一些維護費用很小的資料結構進行插入刪除，直到等於當前區間為止，此時就可以把這個資料結構的答案存到ans陣列裡，然後結束後一次輸出

	for(int i=0,L=1,R=0;i<m;++i){/*這是閉區間的寫法*/
	while(R<q[i].r)add(s[++R]);
	while(L>q[i].l)add(s[--L]);
	while(R>q[i].r)sub(s[R--]);
	while(L<q[i].l)sub(s[L++]);
	ans[q[i].i]=cur_ans;
	}
	for(int i=0;i<m;++i)printf("%d\n",ans[i]);

view raw find query.cpp hosted with ❤ by GitHub

這裡進行一下簡單的證明:

• 假設序列長度為N，我們將序列每K個分成一塊，在排完序後，左界屬於同一塊的詢問，每次都不會移動操過K次；而左界屬於不同塊的操作，從第i塊移動到第i+1塊最多要移動2*K次，總共分成N/K塊，故移動次數加起來不操過2*K*(N/K)=2*N次，因此左界移動的複雜度為$\ord{Q*K}+\ord N$，Q為詢問次數
• 對於右界，在同一塊內因為是遞增的關係所以移動次數不會操過N次，而最多只有N/K塊，因此複雜度為$\ord{N*N/K}$
• 這個時候我們可以取K=sqrt(N)得到一個複雜度為$\ord{Q*K+N+N*N/K}=\ord{(Q+N)*sqrt(N)}$的方法

這是區間眾數的模板(對於每個詢問l,r輸出區間[l,r]眾數的個數):

	#include<bits/stdc++.h>
	using namespace std;
	#define MAXN 100000
	#define MAXQ 100000
	struct Q{
	int l,r,i,block;
	inline bool operator<(const Q &b)const{
	return block==b.block?r<b.r:block<b.block;
	}
	}q[MAXQ+5];
	int s[MAXN+5],lim;
	int ans[MAXQ+5];
	int u[MAXN+5],cnt[MAXN+5],cur_ans;
	inline void add(int x){
	x=++u[x];
	--cnt[x-1];
	++cnt[x];
	cur_ans=max(cur_ans,x);
	}
	inline void sub(int x){
	x=--u[x];
	--cnt[x+1];
	++cnt[x];
	if(!cnt[cur_ans])--cur_ans;
	}
	int n,m;
	int p[MAXN+5],nn;
	int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
	scanf("%d",&s[i]);
	p[i-1]=s[i];
	}
	sort(p,p+n);
	nn=unique(p,p+n)-p;
	for(int i=1;i<=n;++i)s[i]=lower_bound(p,p+nn,s[i])-p;
	lim=1+(int)sqrt(n);
	for(int i=0;i<m;++i){
	scanf("%d%d",&q[i].l,&q[i].r);
	q[i].block=q[i].l/lim;
	q[i].i=i;
	}
	sort(q,q+m);
	for(int i=0,L=1,R=0;i<m;++i){/*這是閉區間的寫法*/
	while(R<q[i].r)add(s[++R]);
	while(L>q[i].l)add(s[--L]);
	while(R>q[i].r)sub(s[R--]);
	while(L<q[i].l)sub(s[L++]);
	ans[q[i].i]=cur_ans;
	}
	for(int i=0;i<m;++i)printf("%d\n",ans[i]);
	return 0;
	}

view raw range mode.cpp hosted with ❤ by GitHub