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

来源:岁月联盟 编辑:猪蛋儿 时间:2012-11-17


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

分析与总结:
枚举所有子序列的起点位置,然后再二分终点位置,使得起点与终点的距离最大,并且这个区间内的最大值与最小值只差满足不超过k。为什么可以二分终点呢? 因为这个是满足单调性的,简单的说,就是越往右边,元素就越多,“不稳定因素”也就越多,差值可能会越来越大。
然后就是要求起点与终点这个区间内的最大值与最小值,明显是RMQ问题。可以用ST算法,nlogn的预处理时间,O(1)的时间查询,效率更高。由于最近在学线段树,而线段树也可以求RMQ问题,所以就用线段树写了。不过线段树每次查询都需要O(logn)的复杂度,效率较低。


代码:
1. 线段树求RMQ 
[cpp]  www.2cto.com
// 线段树求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算法
[cpp] 
// 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;