本文共 4045 字，大约阅读时间需要 13 分钟。
链接：
题目大意：
给n个数，然后找出最长的一段子序列（不需要连续），使得这段子序列中的最大值与最小值之差不超过k。找出有几个子序列满足，并且输出他们的开始位置与结束位置。
分析与总结：
枚举所有子序列的起点位置，然后再二分终点位置，使得起点与终点的距离最大，并且这个区间内的最大值与最小值只差满足不超过k。为什么可以二分终点呢？ 因为这个是满足单调性的，简单的说，就是越往右边，元素就越多，“不稳定因素”也就越多，差值可能会越来越大。
然后就是要求起点与终点这个区间内的最大值与最小值，明显是RMQ问题。可以用ST算法，nlogn的预处理时间，O(1)的时间查询，效率更高。由于最近在学线段树，而线段树也可以求RMQ问题，所以就用线段树写了。不过线段树每次查询都需要O（logn）的复杂度，效率较低。
代码：
1. 线段树求RMQ
// 线段树求RMQ， 812ms#include#include #include #include #include #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算法