这是noip2016的前一天上午，我还是高一的学弟。这次考试结束后，一大批学长就要告别机房，告别高中与代码为伴的时代，告别我们这群整天很能闹腾的学弟学妹们。

我让正值高三的亲爱的大神学长ylf给我份st表的代码，他让我看他博客，我看不懂，于是就有了以下对话。。。。。。

发往: 闫立峰 ( /wjs6-31)（飞鸽传书）

时间: 2016-11-18 星期五 10:19:35  (RSA)(封装)

-------------------------------------

me：那时候的你是不是还年轻啊？代码写的这么恶心看不懂。。。

he：......

me：恩恩 一定是的

me：我是看着你长大的，犹记得你高一的时后还是个小孩啥也不懂，还是伟大的我把你带如了OI的大门，从此你一发不可收拾，成为了众所周知的广饶一中ylf大神！！！

he：哎呀你快省省吧 我现在打一份ST表吧

me：╮(╯▽╰)╭这就对了嘛 这才是标准模范好学长啦啦啦！

 

唉，这么快就要分别了，好舍不得他呀。忘不了他对我的帮助，忘不了他对我们那些鼓励的话。

学哥，加油，你一定可以的，你一定能考上自己心仪的大学！！

以后，不知道你是否会忘记我，但我知道你是我心中最善良的学哥。

学弟在这里默默祝福你了~~~

                                                                                               LRH

                                                                                                2016 11.18

附：不得不加的st表代码

 

#include<cstdio>

#include<cstring>

#define maxn 50010

using namespace std;

int n,m,a[maxn],A[maxn][25],B[maxn][25],p[maxn];

int init(){

　　int x=0,f=1;char s=getchar();

　　while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}

　　while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

　　return x*f;

}

int max(int x,int y){

　　return x>y?x:y;

}

int min(int x,int y){

　　return x<y?x:y;

}

void ST(){

　　memset(A,-127/3,sizeof(A));

　　memset(B,127/3,sizeof(B));

　　for(int i=1;i<=n;i++)

　　A[i][0]=B[i][0]=a[i];

　　for(int j=1;j<=20;j++)

　　for(int i=1;i+(1<<j)-1<=n;i++){

　　A[i][j]=max(A[i][j-1],A[i+(1<<j-1)][j-1]);

　　B[i][j]=min(B[i][j-1],B[i+(1<<j-1)][j-1]);

}

　　for(int i=1;i<=n;i++)

　　for(int j=0;j<=20;j++)

　　if((1<<j)>i){

　　　　p[i]=j-1;break;

　　}

}

int QueryA(int l,int r){

　　int k=p[r-l+1];

　　return max(A[l][k],A[r-(1<<k)+1][k]);

}

int QueryB(int l,int r){

　　int k=p[r-l+1];

　　return min(B[l][k],B[r-(1<<k)+1][k]);

}

int main()

{

　　n=init();m=init();

　　for(int i=1;i<=n;i++)

　　a[i]=init();

　　ST();while(m--){

　　　　int l=init();

　　　　int r=init();

　　　　printf("%d\n",QueryA(l,r)-QueryB(l,r));

　　}

　　return 0;

}

 

http://www.cnblogs.com/yanlifneg/