好奇怪啊，莫名其妙的WA了好几次。。。
两个类似单调队列的东西维护就可以了
后来才发现。。。tmp忘了开始的时候赋值1了（抓狂ing）
1 /************************************************************** 2 Problem: 2096 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1092 ms 7 Memory:79908 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 const int N = 3000005; 15 const int Maxlen = 15 * N + 105; 16 17 int n, k, ans = 1; 18 int a[N], q[2][N], l[2], r[2]; 19 char buf[Maxlen], *c = buf; 20 int Len; 21 22 inline int read() { 23 int x = 0, sgn = 1; 24 while (*c < '0' || '9' < *c) { 25 if (*c == '-') sgn = -1; 26 ++c; 27 } 28 while ('0' <= *c && *c <= '9') 29 x = x * 10 + *c - '0', ++c; 30 return sgn * x; 31 } 32 33 inline void pop_tail_max(int i) { 34 while (l[0] <= r[0] && a[q[0][r[0]]] <= a[i]) 35 --r[0]; 36 q[0][++r[0]] = i; 37 } 38 39 inline void pop_tail_min(int i) { 40 while (l[1] <= r[1] && a[q[1][r[1]]] >= a[i]) 41 --r[1]; 42 q[1][++r[1]] = i; 43 } 44 45 int main() { 46 int i, tmp; 47 Len = fread(c, 1, Maxlen, stdin); 48 buf[Len] = ' '; 49 k = read(), n = read(); 50 for (i = 1; i <= n; ++i) 51 a[i] = read(); 52 l[0] = l[1] = 1, r[0] = r[1] = 0; 53 for (i = tmp = 1; i <= n; ++i) { 54 pop_tail_max(i); 55 pop_tail_min(i); 56 while (a[q[0][l[0]]] - a[q[1][l[1]]] > k) 57 if (q[0][l[0]] < q[1][l[1]]) tmp = q[0][l[0]++] + 1; 58 else tmp = q[1][l[1]++] + 1; 59 ans = max(ans, i - tmp + 1); 60 } 61 printf("%d ", ans); 62 return 0; 63 }