USACO07JAN Balanced Lineup

发表于 | 分类于 |
字数统计: 261 字

题目链接

题解

ST表模板题…
线段树估计会挂，因为询问太多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int f1[16][50005],dat[50005],f2[16][50005],N,Q; 
int max(int a,int b){return (a>b)?a:b;}
int min(int a,int b){return (a<b)?a:b;}
void sttable(int n){
    int i,j,p;
    memcpy(f1[0],dat,sizeof(dat));
    memcpy(f2[0],dat,sizeof(dat));
    for(i=1;(1<<i)<=n;i++)
        for(j=0,p=(1<<(i-1));j<n-p;j++)
            f1[i][j]=max(f1[i-1][j],f1[i-1][j+p]),
            f2[i][j]=min(f2[i-1][j],f2[i-1][j+p]);//同时对最大最小两个st表初始化，递推
}int rmq(int l,int r){
    int k=0;while((1<<(k+1))<(r-l+1))k++;
    return max(f1[k][l],f1[k][r-(1<<k)+1])-min(f2[k][l],f2[k][r-(1<<k)+1]);//询问部分
}int main(){
    scanf("%d%d",&N,&Q);
    int i,l,r;
    for(i=0;i<N;i++)
        scanf("%d",&dat[i]);
    sttable(N);
    for(i=0;i<Q;i++)
        scanf("%d%d",&l,&r),
        printf("%d\n",rmq(l-1,r-1));
    return 0;
}