Solve

POJ3368区间最值-ST算法

题目解答

这是一道可以使用线段树轻松解决的问题，只要维护总最长区间，从左边开始和右边开始的最长区间三个域即可。

但是，还有更巧妙的RMQ解法，假如我们只要[1,n]的最长区间，很显然只要预处理一下，把连续的值的频率算出来，就可以很简单的RMQ了，但问题是：如果区间断开了，那么RMQ是否就失效了?对于断开的区间的整体来说必定是这样，但是其中的完整的子段依然保留着RMQ的最优性。

例如：-1 -1 1 1 1 1 3 10 10 10，预处理后：1 2 1 2 3 4 1 1 2 3，如果查询[5,10]直接ST会算出4，但是应该是3，再仔细观察，因为数列非递减，所以只有左边断开才会影响结果，因此我们只要特殊处理一下左边的连续值即可。然后对剩下的使用ST解决。

运行情况

POJ3368区间最值

程序清单

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<cstdio> 
#include<cmath>
#define Max 100005
#define BIG 40
#define MAX(a,b) ((a)>(b)?(a):(b))
long dp[Max][BIG],num[Max],x,y,n,q;
int main(){
    while(scanf("%ld",&n)&&n){
        scanf("%ld",&q);
        num[0]=-Max;
        for(long i=1;i<=n;i++){
            scanf("%ld",&num[i]); dp[i][0]=1;
            if(num[i]==num[i-1]) dp[i][0]=dp[i-1][0]+1;
        }
        for(long i=1;i<=(long)log2(n);i++)
            for(int j=1;j<=n-(1<<i)+1;j++)
                dp[j][i]=MAX(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
        for(long p=1;p<=q;p++){
            scanf("%ld%ld",&x,&y);
            if(num[x]==num[y]) printf("%ld\n",y-x+1);
            else{
                long l=x,Log;
                while(l++ && (dp[l][0]!=1)) ;
                Log=(long)log2(y-l+1);
                printf("%ld\n",MAX(l-x,MAX(dp[l][Log],dp[y-(1<<Log)+1][Log])));}
    }}
    return 0;
}

难易等级

Middle Up(Noip the 3rd)