（那一天我唯一彻底搞懂的东西然而现在也忘光光）
先看题：（RP++）
先跳过暴力，这一题肯定不行的
这时就需要ST表，ST表：Sparse Table Algorithm
关于长度2k解释：因为要完全覆盖整个区间，而对于求最大值和最小值两个区间有交集是没有影响的（不是精确覆盖），所以可以求2k<=r-l+1
例题：（裸的ST表）
代码：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int a[1000001]; int Fmax[100005][25]; int Fmin[100005][25]; int n,m; void MM() { for(int j=1;j<=floor(log(n)/log(2));j++) for(int i=1;i+(1<<j)-1<=n;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 main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); Fmax[i][0]=a[i]; Fmin[i][0]=a[i]; } MM(); int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); int k=floor(log(y-x+1)/log(2)); printf("%d\n",max(Fmax[x][k],Fmax[y-(1<<k)+1][k])); } return 0; }
再看一道题？
大概思路：
（代码有时间再放吧。。要月考了。。。）
原文：https://www.cnblogs.com/Daz-Os0619/p/11469735.html