RMQ（区间最值查询），可以用线段树和ST表解决

• 线段树 预处理 O (nlogn) 查询 O (logn) 支持在线修改

• ST表 预处理 O (nlogn) 查询O(1) 不支持在线修改

1.区间最值差—可用线段树，但ST更短

#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
const int N = 50010;
int a[N];
int n,m;
int Fmax[N][20];
int Fmin[N][20];
void init()
{for(int i=1;i<N;i++)Fmax[i][0]=Fmin[i][0]=a[i];int k=log2(n);for(int j=1;j<=k;j++)for(int i=1;i<=n-(1<<j)+1;i++){Fmax[i][j]=max(Fmax[i][j-1],Fmax[i+(1<<j-1)][j-1]);Fmin[i][j]=min(Fmin[i][j-1],Fmin[i+(1<<j-1)][j-1]);}}
int RMQ(int l,int r)
{int k=log2(r-l+1);int m1=max(Fmax[l][k],Fmax[r-(1<<k)+1][k]);int m2=min(Fmin[l][k],Fmin[r-(1<<k)+1][k]);return m1-m2;
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",a+i);init();while(m--){int l,r;scanf("%d%d",&l,&r);printf("%d\n",RMQ(l,r));}
}

2.最频繁值

#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
const int N = 100010;
int a[N],cnt[N]={0};
int n,m;
int f[N][20];
int lg2[N];
void init_log()
{lg2[0]=-1;for(int i=1;i<N;i++)lg2[i]=lg2[i>>1]+1;
}
void init_ST()
{for(int i=1;i<=n;i++)f[i][0]=cnt[i];for(int j=1;j<=lg2[n];j++)for(int i=1;i+(1<<j)-1<N;i++)f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int RMQ(int l,int r)
{int k=lg2[r-l+1];return max(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{scanf("%d",&m);for(int i=1;i<=n;i++){   scanf("%d",a+i);if(a[i]!=a[i-1])cnt[i]=1;else cnt[i]=cnt[i-1]+1;}init_ST();while (m -- ){int l,r;scanf("%d%d",&l,&r);int t=l;while(a[t]==a[l-1]&&t<=r)t++;if(t>r)printf("%d\n",t-l);else printf("%d\n",max(t-l,RMQ(t,r)));}
}
signed main()
{init_log();while(cin>>n,n)solve();
}

3.炸鸡块君与FIFA22

#include <iostream>
using namespace std;
const int N = 200010;
int f[3][N][20];
char s[N];
signed main()
{int n,m;cin>>n>>m;cin>> s+1 ;for(int j=0;j<3;j++)for(int i=1;i<=n;i++){if(s[i]=='W')f[j][i][0]=1;else if(s[i]=='L'){if(!j)f[j][i][0]=0;else f[j][i][0]=-1;}else f[j][i][0]=0;}//类似于区间DP   初始化ST表for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++)for(int k=0;k<3;k++)f[k][i][j]=f[k][i][j-1]+f[(k+f[k][i][j-1])%3][i+(1<<j-1)][j-1];// query STint l,r,x;while(m--){scanf("%d%d%d",&l,&r,&x);for(int j=20;j>=0;j--){if(l+(1<<j)-1>r)continue;x+=f[x%3][l][j];l+=(1<<j);}printf("%d\n",x);}
}