題目大意：
給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;
}
