/* 开始以为是二分...后来发现丫不单调... */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1000010 using namespace std; int n,l,r,ans,tmin[maxn],tmax[maxn],a[maxn]; int qmin[maxn],qmax[maxn],headmin,tailmin,headmax,tailmax; int ansmin[maxn],ansmax[maxn],lm; int init() { int f=1,x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int Judge(int k) { int x;lm=0;int falg=0; tailmin=0;headmin=1; tailmax=0;headmax=1; for(int i=1;i<=k-1;i++) { x=a[i]; while(x>qmax[tailmax]&&tailmax>0) {tailmax--;if(tailmax<headmax&&headmax>1)headmax--;} qmax[++tailmax]=x;tmax[tailmax]=i; if(i-tmax[headmax]+1>k)headmax++; while(x<qmin[tailmin]&&tailmin>0) {tailmin--;if(tailmin<headmin&&headmin>1)headmin--;} qmin[++tailmin]=x;tmin[tailmin]=i; if(i-tmin[headmin]+1>k)headmin++; } for(int i=k;i<=n;i++) { x=a[i]; while(x>qmax[tailmax]&&tailmax>0) {tailmax--;if(tailmax<headmax&&headmax>1)headmax--;} qmax[++tailmax]=x;tmax[tailmax]=i; if(i-tmax[headmax]+1>k)headmax++; ansmax[++lm]=qmax[headmax]; while(x<qmin[tailmin]&&tailmin>0) {tailmin--;if(tailmin<headmin&&headmin>1)headmin--;} qmin[++tailmin]=x;tmin[tailmin]=i; if(i-tmin[headmin]+1>k)headmin++; ansmin[lm]=qmin[headmin]; } for(int i=1;i<=lm;i++) { int tmp=ansmax[i]-ansmin[i]; if(tmp>=l&&tmp<=r){falg=1;break;} } return falg; } int main() { while(~scanf("%d%d%d",&n,&l,&r)) { for(int i=1;i<=n;i++)a[i]=init(); int li=0,ri=n;ans=0; while(li<=ri) { int mid=(li+ri)/2; if(!Judge(mid)) { ans=max(ans,mid); li=mid+1; } else ri=mid-1; } printf("%d ",ans); } return 0; }
/* 开始想的是直接单调队列 but 最大最小值的所在序列不确定 不能搞出长度 不好办 其实可以维护出来的 对于序列的右端点是确定的 是i 而左端点开始默认是1 不断更新就好了 考虑超出r的 设于队头的元素的位置分别为pmax pmin 不断删除队头 并更新n指针 直到在范围里 这是 指针位置就是序列的左端点 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1000010 using namespace std; int n,l,r,ans,tmin[maxn],tmax[maxn],a[maxn]; int qmin[maxn],qmax[maxn],headmin,tailmin,headmax,tailmax; int init() { int f=1,x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void Solve() { int x,now=1; tailmin=0;headmin=1; tailmax=0;headmax=1; for(int i=1;i<=n;i++) { x=a[i]; while(x>qmax[tailmax]&&tailmax>=headmax)tailmax--; qmax[++tailmax]=x;tmax[tailmax]=i; while(x<qmin[tailmin]&&tailmin>=headmin)tailmin--; qmin[++tailmin]=x;tmin[tailmin]=i; while(headmin<=tailmin&&headmax<=tailmax&&qmax[headmax]-qmin[headmin]>r) { if(tmax[headmax]<=tmin[headmin]){now=tmax[headmax]+1;headmax++;} else {now=tmin[headmin]+1;headmin++;} } if(qmax[headmax]-qmin[headmin]>=l)ans=max(ans,i-now+1); } } int main() { while(~scanf("%d%d%d",&n,&l,&r)) { for(int i=1;i<=n;i++)a[i]=init(); ans=0;Solve(); printf("%d ",ans); } return 0; }