打出st表的步骤：1：建立初始状态，2：区间按2的幂从小到大求出值 3：查询时按块查找即可
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define maxn 50010 int mx[maxn][20],mi[maxn][20],d[maxn]; void initmax(int n,int d[]){ for(int i=1;i<=n;i++) mx[i][0]=d[i]; for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++) mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); } int getmax(int L,int R){ int k=0; while((1<<(k+1))<=R-L+1) k++; return max(mx[L][k],mx[R-(1<<k)+1][k]); } void initmin(int n,int d[]){ for(int i=1;i<=n;i++) mi[i][0]=d[i]; for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++) mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]); } int getmin(int L,int R){ int k=0; while((1<<(k+1))<=R-L+1) k++; return min(mi[L][k],mi[R-(1<<k)+1][k]); } int main(){ int n,q; while(scanf("%d%d",&n,&q)!=EOF){ for(int i=1;i<=n;i++) scanf("%d",&d[i]); initmax(n,d);initmin(n,d); while(q--){ int L,R; scanf("%d%d",&L,&R); printf("%d\n",getmax(L,R)-getmin(L,R)); } } return 0; }
转载于:https://www.cnblogs.com/zsben991126/p/10019676.html
