RMQ(区间最值查询),可以用线段树和ST表解决
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 ST
int 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);
}
}