第12期：ST表

ST表算法详解

ST表详解+模板

ST表 「 从入门到入门 · 浅显理解 」

浅谈ST表

某个区间查询问题是否适用ST表，关键在于其进行的操作是否允许区间重叠，例如max(a,b,c) = max{max(a,b),max(b,c)}就可以用ST表维护，而区间和问题则不能维护。

问题描述
给定一个长度为n的序列，有m次询问，每次给定区间[L , R]，求区间内最大值。
算法思路
定义st表
我们设 st[i][j] 为从 i 开始的向后 2^j 个数中的最大值。假设这n个数存放的序列a中，根据定义 st[i][j] = max{a[k] | i <= k <= i+2^j - 1}。

#include
#include
#include
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int Max[MAXN][21];
int Query(int l,int r)
{
    int k=log2(r-l+1); 
    return max(Max[l][k],Max[r-(1< 
例题 
1 P3865 【模板】ST 表 
//ST表模板解法 
#include
#include
#include
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int Max[MAXN][21];
int Query(int l,int r)
{
    int k=log2(r-l+1); 
    return max(Max[l][k],Max[r-(1< 
2 P2251 质量检测 
//ST表模板解法 167ms /  10.42MB /  798B C++14 (GCC 9)
#include
#include
#include
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int Min[MAXN][21];
int Query(int l,int r)
{
    int k=log2(r-l+1); 
    return min(Min[l][k],Min[r-(1< 
//更快解法  78ms /  4.85MB /  602B C++20
#include
#define For(i,a,b) for (int i=(a);i<=(b);i++)
using namespace  std;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=2e6+10;
int n,k;
int ar[N],s[N],head,top;

int main()
{
	head=0,top=-1;
	n=read();k=read();
	For(i,1,n) ar[i]=read();
	
	For(i,1,n)
	{
		if (head<=top && i-k>=s[head])head++;
		while(head<=top && ar[i]<=ar[s[top]])top--;
		s[++top]=i;
		if (i>=k)printf("%dn",ar[s[head]]);
	}
	
	return 0;
}
 
3 P7974 [KSN2021] Delivering Balls  
题解
 
#include
#define he(i,j) (h[st[i][j]]+st[i][j])
#define eh(i,j) (h[ts[i][j]]+n-ts[i][j])
#define hh(i,j) (h[tt[i][j]])
#define ll long long 
using namespace std;
ll st[300000][20];
ll ts[300000][20];
ll tt[300000][20];
ll d[300000];
ll h[300000];
ll n;
ll maxnn(ll a,ll b){
	if(a==b)return ts[a][0];
	ll le=b-a+1;ll o=(b-(1<he(o,d[le])){
		return st[a][d[le]];
	}else return st[o][d[le]];
}
ll maxn(ll a,ll b){
	if(a==b)return st[a][0];
	ll le=b-a+1;ll o=b-(1<eh(o,d[le])){
		return ts[a][d[le]];
	}else return ts[o][d[le]];
}
ll maxt(ll a,ll b){
	if(a==b)return tt[a][0];
	ll le=b-a+1;ll o=b-(1<hh(o,d[le])){
		return tt[a][d[le]];
	}else return tt[o][d[le]];
}
ll len(ll a,ll b,ll f){//这里我是直接分别求这四段的路径长度 
	if(a==b)return 0;//和题解不同 
	ll ans=0;
	ans+=(b-a)*2;
	if(h[a]b-a)ans+=(h[b]-h[a]-(b-a))*1LL*2;
	}else{
		ans+=(h[a]-h[b])*(-1+3*f);
		if(h[a]-h[b]>b-a)ans+=(h[a]-h[b]-(b-a))*1LL*2;	
	} 
	return ans;
}
int main(){
	ll q;
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>h[i];
		st[i][0]=ts[i][0]=tt[i][0]=i;
	}
	for(ll i=1;i<=19;i++){//三个ST表 
		ll le=1<<(i-1);
		for(ll j=1;j+le*2-1<=n;j++){
			if(he(j,i-1)>he(j+le,i-1)){
				st[j][i]=st[j][i-1];
			}else st[j][i]=st[j+le][i-1];
			if(eh(j,i-1)>eh(j+le,i-1)){
				ts[j][i]=ts[j][i-1];
			}else ts[j][i]=ts[j+le][i-1];
			if(hh(j,i-1)>hh(j+le,i-1)){
				tt[j][i]=tt[j][i-1];
			}else tt[j][i]=tt[j+le][i-1];
		}
	}
	ll le=0,g=1;
	for(ll i=1;i<=n;i++){//预处理对数 
		if(2*g>q;
	for(ll i=1;i<=q;i++){
		ll a,b;cin>>a>>b;
		ll lo=0;
		if(a>b){
			swap(a,b);lo=1;
		}
		ll yg=maxnn(a,b),zg=maxn(a,b);
		ll zz=maxt(zg,yg);
	//	cout<
 
#include
using namespace std;
typedef long long ll;
const int maxn=200005;

int n,q,s,t;
int h[maxn];
int f[maxn][31],f1[maxn][31],f2[maxn][31],log_2[maxn];
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main (){
    n=read();
    for(int i=1;i<=n;i++){
    	h[i]=read();
    	f[i][0]=h[i];
    	f1[i][0]=h[i]-i;
    	f2[i][0]=h[i]+i;
	}
	for(int i=1;i<=30;i++){
		for(int j=1;j+(1<r)swap(l,r);
		int len=log_2[r-l+1];
		
		mh=max(f[l][len],f[r-(1<t)swap(ms,mt);
		cnt= abs(t-s)-((mh-ms-h[s]) + (mh-mt-h[t])); 
		ans = 4*(mh-h[s]) + (mh-h[t]) + 2*cnt; 
		printf("%lldn",ans);
	}
    return 0;
}
 
4 P3295 [SCOI2016]萌萌哒 题解 
 
5 P4501 [ZJOI2018]胖