脚本宝典收集整理的这篇文章主要介绍了[总结] 四毛子算法，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

[总结] 四毛子算法

【模板】ST 表

四毛子算法，又叫 **the Method of Four Russians **，复杂度为 (text O(n+m))，可以在线性时间内求解 RMQ 问题。

四毛子重要的不是算法，重要的是一种序列问题的转化思想。

1. 笛卡尔树

把原序列的笛卡尔树建出来，堆顶大小根据题目而定。

对于原序列的一个区间 ([L,R])，在笛卡尔树中找到其对应位置，它们的 (LCA) 就是求解的答案。

2. (LCA) 问题的处理

在 Enler 序上解决，也就是欧拉序，也就是在欧拉序上的一个新的 RMQ 问题。

而在欧拉序上的 RMQ 求解的就不是 (value) 的 RMQ 问题了，而是找到区间 ([L,R]) 深度最小的点。

四毛子算法的主要思想就基于此：原来的不规则 RMQ 问题转化为了 (±1) RMQ 问题，也就是说，相邻两个点最多变化 (1)，且一定变化。

3. (±1) RMQ 问题求解

设 (t) 为 Enler 序列的长度，取块长 (b=lceilfrac{LOG_2t}{2}rceil)。对欧拉序列进行分块，使用 ST 表处理大块间的信息维护，复杂度为 (text O(frac{t}{b}log t)=text O(n))。

对于那些边角块的处理，需要通过预处理达到 (text O(1)) 的复杂度，由于差分数组总共只有 (2^{b-1}) 种，所以预处理的复杂度可以达到 (text O(b2^b))，不超过 (text O(n))。

具体来说，可以把每一个序列形成的规则折线状压起来，如果第 (i) 位是 (1) 表示 (i->i+1) 折线下降了 (1)，反之表示序列上升了 (1)。

最后用常规思路处理边角块问题即可。

4. 细节

对于原序列上的区间 ([L,R])，(DFn_L) 不一定小于 (dfn_R)。

const int maxn = 2e5 + 10;
const int maxb = 17;
struct node{
	int val,de,dfn;
	int son[2];
}t[maxn];
int stk[maxn],top,rt;
int n,m;
void build(){
	for(int i=1;i<=n;i++){
		while(top @R_512_315@ t[i].val>t[stk[top]].val)t[i].son[0]=stk[top--];
		if(top)t[stk[top]].son[1]=i;
		stk[++top]=i;
	}
	rt=stk[1];//the top of the right segment
}
int idx;
node a[maxn];
void dfs(int u){
	t[u].dfn=++idx;a[idx]=t[u];
	for(int i=0;i<2;i++){
		if(t[u].son[i]){
			t[t[u].son[i]].de=t[u].de+1;
			dfs(t[u].son[i]);
			a[++idx]=t[u];
		}
	}
}
int n1,blocks[maxn],L[maxn],R[maxn];
node f[maxn][maxb+1];
node min(node a,node b){
	return (a.de<b.de)?a:b;
}
void ST_inIT(){
	n1=(int)(ceil(log2(idx)/2));
	for(int i=1;i<=idx;i++){
		blocks[i]=(i-1)/n1+1;
		if(!L[blocks[i]])L[blocks[i]]=i;
		R[blocks[i]]=i;
	}
	for(int i=1;i<=blocks[idx];i++){
		f[i][0]=a[L[i]];
		for(int j=L[i]+1;j<=R[i];j++)f[i][0]=min(f[i][0],a[j]);
	}
	int tmp=(int)log2(idx+0.5);
	for(int j=1;j<=tmp;j++){
		for(int i=1;i<=blocks[idx];i++){
			if(i+(1<<j-1)-1<=idx)
				f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
}
int Pos[(1<<;maxb)+10],Dif[maxn];
void small_init(){
	for(int i=1;i<=blocks[idx];i++){
		for(int j=L[i]+1;j<=R[i];j++){
			if(a[j].de<a[j-1].de)Dif[i]|=(1<<j-1-L[i]);
		}
	}
	for(int s=0;s<(1<<n1-1);s++){//state:b-1 bits
		int mx=0,v=0;
		for(int i=1;i<n1;i++){
			v+=(s>>i-1&amp;1)?(-1):1;
			if(mx>v)mx=v,Pos[s]=i;
		}
	}
}
node ST_query(int l,int r){
	int c=log2(r-l+1+0.5);
	return min(f[l][c],f[r-(1<<c)+1][c]);
}
node small_query(int l,int r){
	int p=blocks[l],S=(Dif[p]>>(l-L[p])) & ((1<<r-l)-1);
	//cerr<<l<<" "<<r<<" "<<Pos[S]<<endl;//
	return a[Pos[S]+l];
}
node query(int l,int r){
	if(l>r)return query(r,l);
	if(blocks[l]==blocks[r])return small_query(l,r);
	else {
		node s=min(small_query(l,R[blocks[l]]),small_query(L[blocks[r]],r));
		if(blocks[r]-blocks[l]>1)s=min(s,ST_query(blocks[l]+1,blocks[r]-1));
		return s;
	}
}
#define read() read<int>()
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)t[i].val=read();
	build();dfs(rt);
	ST_init();small_init();
	while(m--){
		int l=read(),r=read();
		PRintf("%dn",query(t[l].dfn,t[r].dfn).val);
	}
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的[总结] 四毛子算法全部内容，希望文章能够帮你解决[总结] 四毛子算法所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。