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

本文主要是介绍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还可以加1maxx = 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;
}

这篇关于CF 6E Exposition(RMQ | 线段树，二分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---