http://acm.hust.edu.cn/vjudge/problem/11253
这题要找到区间和在[m,k]范围内的最长区间
用两个单调序列保存区间最大值和最小值。当最大值-最小值》k时更新head，如果最大值-最小值>=m更新答案
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 1000000+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m,k; int p1[MAXN],p2[MAXN],a[MAXN],ans; void getL() { int h1,h2,r1,r2,pre; h1=h2=pre=1; r1=r2=ans=0; for(int i=1;i<=n;i++) { while(h1<=r1 && a[i]<=a[p1[r1]]) r1--; p1[++r1] = i; while(h2<=r2 && a[i]>=a[p2[r2]]) r2--; p2[++r2] = i; while(h1<=r1 && h2<=r2 && a[p2[h2]] - a[p1[h1]] > k) { if(p1[h1]>p2[h2]) pre = p2[h2++]+1; else pre = p1[h1++]+1; } if(h1<=r1 && h2<=r2 && a[p2[h2]] - a[p1[h1]]>=m) { ans = max(ans,i-pre+1); } } } int main() { int i,j,t,kase=1; while(~sf("%d%d%d",&n,&m,&k)) { for(i=1;i<=n;i++) sf("%d",&a[i]); getL(); pf("%d ",ans); } return 0; }