CF 6E Exposition(RMQ | 线段树，二分)

链接：

http://codeforces.com/problemset/problem/6/E

题目大意：

给n个数，然后找出最长的一段子序列（不需要连续），使得这段子序列中的最大值与最小值之差不超过k。找出有几个子序列满足，并且输出他们的开始位置与结束位置。

分析与总结：

枚举所有子序列的起点位置，然后再二分终点位置，使得起点与终点的距离最大，并且这个区间内的最大值与最小值只差满足不超过k。为什么可以二分终点呢？ 因为这个是满足单调性的，简单的说，就是越往右边，元素就越多，“不稳定因素”也就越多，差值可能会越来越大。

然后就是要求起点与终点这个区间内的最大值与最小值，明显是RMQ问题。可以用ST算法，nlogn的预处理时间，O(1)的时间查询，效率更高。由于最近在学线段树，而线段树也可以求RMQ问题，所以就用线段树写了。不过线段树每次查询都需要O（logn）的复杂度，效率较低。

代码：

1. 线段树求RMQ

// 线段树求RMQ， 812ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define mem(str,x) memset(str,(x),sizeof(str))
#define FOR(i,s,t) for(int i=(s); i<(t); ++i)
#define FF(i,n) for(int i=0; i<(n); ++i)
#define mid ((left+right)>>1)
#define len (right-left+1)
#define lson rt<<1, left, m
#define rson rt<<1|1, m+1, right
#define STOP puts("Stop Here~");
const int dir4[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; //上下左右
const int dir8[8][2] = {{-1,0},{1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
using namespace std;

//=========================================================
const int MAXN = 100005;
int n,k;
int Max[MAXN<<2],Min[MAXN<<2],maxx,minx;
int ans_max,pos,loc[MAXN][2];

void build(int rt,int left,int right){
    if(left==right){
        scanf("%d",&Max[rt]);
        Min[rt] = Max[rt];
        return;
    }
    int m = mid;
    build(lson); build(rson);
    Max[rt] = max(Max[rt<<1],Max[rt<<1|1]);
    Min[rt] = min(Min[rt<<1],Min[rt<<1|1]);
}

void query(int rt,int left,int right,int l,int r){
    if(left==l && right==r){
        maxx = max(maxx,Max[rt]); 
        minx = min(minx,Min[rt]);
        return;
    }
    int m = mid;
    if(r <= m) query(lson,l,r);
    else if(l > m) query(rson,l,r);
    else query(lson,l,m),query(rson,m+1,r);
}

void binary(int p,int left,int right){
    
    while(left < right){
        int m = mid;
        maxx=-1, minx=10000000;
        query(1,1,n,p,m);
     //   printf("%d\n",maxx-minx);
        int dif = maxx-minx;
        if(dif > k) right=m;
        else left=m+1;
    }
    if(left-p>ans_max){
        ans_max=left-p;
        pos=0;
        loc[pos][0]=p,loc[pos][1]=left-1;
    }
    else if(left-p==ans_max){
        ++pos;
        loc[pos][0]=p,loc[pos][1]=left-1;
    }
}

int main(){
    while(~scanf("%d%d",&n,&k)){
         build(1,1,n);
         ans_max=0;
         FOR(i,1,n+1){
             binary(i,i,n+1);
         } 
         printf("%d %d\n",ans_max,pos+1);

         for(int i=0; i<=pos; ++i)
             printf("%d %d\n",loc[i][0],loc[i][1]);
      //   puts("");
    }
    return 0;
}

2.ST算法

// ST算法求RMQ， 390ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define mem(str,x) memset(str,(x),sizeof(str))
#define FOR(i,s,t) for(int i=(s); i<(t); ++i)
#define FF(i,n) for(int i=0; i<(n); ++i)
#define mid ((left+right)>>1)
#define len (right-left+1)
#define lson rt<<1, left, m
#define rson rt<<1|1, m+1, right
#define STOP puts("Stop Here~");
const int dir4[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; //上下左右
const int dir8[8][2] = {{-1,0},{1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
using namespace std;

//=========================================================
const int MAXN = 200010;
int n,k;
int Max[MAXN][20],Min[MAXN][20],maxx,minx;
int ans_max,pos,loc[MAXN][2];
int A[MAXN];

int RMQ_init(){
    for(int i=1; i<=n; ++i)Max[i][0]=A[i],Min[i][0]=A[i];
    for(int j=1; (1<<j)<=n; ++j)
        for(int i=1; i+j-1<=n; ++i){
            Max[i][j] = max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
            Min[i][j] = min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);
        }
}
void query(int L,int R){
    int k = 0;
    while((1<<(k+1)) <= R-L+1)++k; //如果2^(k+1)<=R-L+1,那么k还可以加1
    maxx = max(maxx,max(Max[L][k],Max[R-(1<<k)+1][k]));
    minx = min(minx,min(Min[L][k],Min[R-(1<<k)+1][k]));
}

// 二分求出所有答案
void binary(int p,int left,int right){
    while(left < right){
        int m = mid;
        maxx=-1, minx=10000000;
        query(p,m);
        int dif = maxx-minx;
        if(dif > k) right=m;
        else left=m+1;
    }
    if(left-p>ans_max){
        ans_max=left-p;
        pos=0;
        loc[pos][0]=p,loc[pos][1]=left-1;
    }
    else if(left-p==ans_max){
        ++pos;
        loc[pos][0]=p,loc[pos][1]=left-1;
    }
}

int main(){
    while(~scanf("%d%d",&n,&k)){
        FOR(i,1,n+1) scanf("%d",&A[i]);
        RMQ_init();
        ans_max=0;
        FOR(i,1,n+1){
            binary(i,i,n+1);
        } 
        printf("%d %d\n",ans_max,pos+1);
        for(int i=0; i<=pos; ++i)
            printf("%d %d\n",loc[i][0],loc[i][1]);
    }
    return 0;
}

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)

分享到：

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)