n 个数字 取一段区间 求最大最小的差 <=k
问最大的长度 这样长度的区间有几个
问长度最长的区间的l r
1 题目看不懂
2 看题解 线段树+二分 其实我也没碰到过这种的
线段树维护 l r 最大值和最小值
然后二分 i 到 l r 这一段区间能到的最右边的值 维护一下
#include#include #include #include #include using namespace std;#define LL long long#define MAXN 100010#define inf 1000000000struct node{ int l,r,mx,mi;}tree[MAXN<<2];void Build(int l,int r,int a){ tree[a].l=l; tree[a].r=r; if(l==r) { scanf("%d",&tree[a].mi); tree[a].mx=tree[a].mi; return ; } int mid = (l+r)>>1; Build(l,mid,a<<1); Build(mid+1,r,a<<1|1); tree[a].mi=min(tree[a<<1].mi,tree[a<<1|1].mi); tree[a].mx=max(tree[a<<1].mx,tree[a<<1|1].mx);}int mi,mx;void Ques(int l,int r,int L,int R,int a){ if(L<=l&&r<=R) { mi=min(mi,tree[a].mi); mx=max(mx,tree[a].mx); return ; } int mid=(l+r)>>1; if(L<=mid) Ques(l,mid,L,R,a<<1); if(R>mid) Ques(mid+1,r,L,R,a<<1|1);}int enl[MAXN],enr[MAXN];int main(){ int n,k; while(scanf("%d%d",&n,&k)!=EOF) { Build(1,n,1); int ans=0,cnt=0; for(int i=1;i<=n;i++) { int l=i,r=n,a1; a1=0; while(l<=r) { int mid=(l+r)>>1; mi=inf; mx=-inf; Ques(1,n,i,mid,1); if(mx-mi>k) r=mid-1; else { a1=max(a1,mid); l=mid+1; } } mi=inf; mx=-inf; if(a1==n+1) a1--; Ques(1,n,i,a1,1); if(mx-mi<=k) { if(a1-i+1>ans) { cnt=0; ans = a1-i+1; enl[cnt]=i; enr[cnt++]=a1; } else if(a1-i+1==ans) { enl[cnt]=i; enr[cnt++]=a1; } } } printf("%d %d\n",ans,cnt); for(int i=0;i