首页 > 代码库 > 6E-差值不超过k的子段个数

6E-差值不超过k的子段个数

给n个数,然后找出最长的一段子序列(不需要连续),使得这段子序列中的最大值与最小值之间的差值不超过k.找出有几个子序列满足,并输出他们的开始位置和结束位置

#include <cstdio>#include <iostream>using namespace std;int n,k,a[100005];int Max[100005],Min[100005],h1,t1,h2,t2,j;inline int Get_Max(){    return a[Max[h1+1]];}inline int Get_Min(){    return a[Min[h2+1]];}inline void Update(){    while (Max[h1+1]<j) h1++;    while (Min[h2+1]<j) h2++;}inline void Push(int x){    while (h1!=t1 && a[x]>=a[Max[t1]]) t1--;    Max[++t1]=x;    while (h2!=t2 && a[x]<=a[Min[t2]]) t2--;    Min[++t2]=x;}int ans=1;int _O_[100005],_cnt=0;int main(){    scanf("%d%d",&n,&k);    for (int i=1;i<=n;i++) scanf("%d",a+i);    Push(1);    _O_[_cnt=1]=1;    Max[t1=1]=Min[t2=1]=1;    j=1;    for (int i=2;i<=n;i++)    {        Push(i);        while (Get_Max()-Get_Min()>k) j++,Update();        if (i-j+1>ans)        {            ans=i-j+1;            _O_[_cnt=1]=j;        }        else if (i-j+1==ans)        {            _O_[++_cnt]=j;        }    }    printf("%d %d\n",ans,_cnt);    for (int i=1;i<=_cnt;i++)        printf("%d %d\n",_O_[i],_O_[i]+ans-1);    return 0;}

 

6E-差值不超过k的子段个数