好久没写题解了……

净去颓颓颓了……

这题是ST裸题，顺便复习一下ST。

那个I/O优化提示就是赤裸裸的威胁，赤裸裸的威胁啊！

代码：

/**************************************************************
    Problem: 1699
    User: danihao123
    Language: C++
    Result: Accepted
    Time:720 ms
    Memory:7640 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=50001,maxlogn=17;
int n;
int A[maxn],maxv[maxn][maxlogn],minv[maxn][maxlogn];
void Init_Table(){
    register int i,j,pos;
    for(i=1;i<=n;i++)
        maxv[i][0]=minv[i][0]=A[i];
    for(j=1;(1<<j)<=n;j++)
        for(i=1;(i+(1<<j)-1)<=n;i++){
            pos=i+(1<<(j-1));
            maxv[i][j]=max(maxv[i][j-1],maxv[pos][j-1]);
            minv[i][j]=min(minv[i][j-1],minv[pos][j-1]);
        }
}
int query(int l,int r){
    register int k=0,pos;
    while((1<<(k+1))<=(r-l+1))
        k++;
    pos=r-(1<<k)+1;
    return max(maxv[l][k],maxv[pos][k])-min(minv[l][k],minv[pos][k]);
}
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
    register int i,q,l,r;
    n=readint();
    q=readint();
    for(i=1;i<=n;i++)
        A[i]=readint();
    Init_Table();
    while(q--){
        l=readint();
        r=readint();
        writeint(query(l,r));
        putchar('\n');
    }
    return 0;
}

• 相关文章
• 全局相关文章