A

题目链接：https://vjudge.net/contest/202699#problem/A

题意

给一个n个元素的序列，从中挑出最长的子序列，要求子序列中元素差的最大值不超过k。问有几个最长子序列，子序列长度，以及这几个子序列的起始、终止位置。

n<=10e5,k<=10e6

题解

很显然是水题。。

方法1.rmq+二分查找

很暴力很暴力的做法。若用st表维护时间复杂度为（nlogn）,线段树（nlognlogn）

即维护出每一段区间的最小最大值

每次查找时确定头结点，二分尾节点

方法2.滑动窗口+单调队列

时间复杂度（n）

很容易发现这是个滑动窗口问题，即固定左端点，向右延伸右端点

若无法延伸，则移动左端点，而右端点维持原状

其中当前区域内的最小值和最大值显然用单调队列维护

代码

方法1：

 1 #include<iostream> 
 2 #include<cstdio>
 3 typedef struct re {int x,h,t;};
 4 int a[200000],f[200000];
 5 re p1[2000000],p2[2000000];
 6 using namespace std;
 7 int n,k;
 8 void build1(int x,int h,int t)
 9 {  
10   p1[x].h=h; p1[x].t=t;
11   if (h==t)
12   {
13     p1[x].x=a[h]; return;
14   }
15   int mid=(h+t)/2;
16   build1(x*2,h,mid); build1(x*2+1,mid+1,t);
17   p1[x].x=max(p1[x*2].x,p1[x*2+1].x);
18 }
19 void build2(int x,int h,int t)
20 {  
21   p2[x].h=h; p2[x].t=t;
22   if (h==t)
23   {
24     p2[x].x=a[h]; return;
25   }
26   int mid=(h+t)/2;
27   build2(x*2,h,mid); build2(x*2+1,mid+1,t);
28   p2[x].x=min(p2[x*2].x,p2[x*2+1].x);
29 }
30 int query1(int x,int h,int t)
31 {
32   if (p1[x].h>t || p1[x].t<h) return(0);
33   if (h<=p1[x].h && p1[x].t<=t) return(p1[x].x);
34   return(max(query1(x*2,h,t),query1(x*2+1,h,t))); 
35 }
36 int query2(int x,int h,int t)
37 {
38   if (p2[x].h>t || p2[x].t<h) return(11111111);
39   if (h<=p2[x].h && p2[x].t<=t) return(p2[x].x);
40   return(min(query2(x*2,h,t),query2(x*2+1,h,t))); 
41 }
42 bool check(int x,int y)
43 {
44   if (query1(1,x,y)-query2(1,x,y)<=k) return(true);
45   else return(false);
46 }
47 main(){
48   scanf("%d%d",&n,&k);
49   for (int i=1; i<=n; i++)
50     scanf("%d",&a[i]);
51   build1(1,1,n);
52   build2(1,1,n);
53   int maxn=0;
54   for (int i=1; i<=n; i++)
55   {
56     int h=0,t=n-i;
57     while (h<t)
58     {
59       int mid=(h+t)/2+1;
60       if (check(i,i+mid)) h=mid; else t=mid-1; 
61     }
62     f[i]=h+1; maxn=max(maxn,f[i]);
63   }
64   int cnt=0;
65   for (int i=1; i<=n; i++) 
66     if (f[i]==maxn) cnt++;
67   printf("%d %d
",maxn,cnt);
68   for (int i=1; i<=n; i++)
69     if (f[i]==maxn) printf("%d %d
",i,f[i]+i-1);  
70   return(0);
71 }