锐客网

  1. 首页 > it技术 > >

hdu5289|hdu5289 Assignment（极差＜k的子区间数量，单调性证明+双指针+单调队列）

题意： 【hdu5289|hdu5289 Assignment（极差＜k的子区间数量，单调性证明+双指针+单调队列）】给定长度为n的序列a，问有多少个子区间，满足该子区间的最大值和最小值的差值 数据范围：n<=1e5，0<=a(i)<=1e9，0 解法：

设[l,r]的极差为p,那么[l+1,r]的极差一定<=p, 证明: 1.如果a[l]不是极值,那么对极差没有影响 2.如果a[l]是极值,那么极差变小那么对于一个固定的右端点r: 1.如果左端点l满足,那么l+1也满足, 2.如果左端点l不满足,那么l-1也不满足, 综上得:左端点l满足单调性证明出了单调性就有很多解法了: 解法1: 枚举r,二分l,check就是判断ma(l,r)-mi(l,r)=k, ma()和mi()需要rmq数据结构.解法3: 枚举r,指针维护l,指针向右移动得条件是ma(l,r)-mi(l,r)>=k, [l,r]的ma和mi用两个单调队列维护解法3是O(n)的,比前面两种都快,代码用的解法3.

code：
#include using namespace std; #define int long long const int maxm=1e5+5; int a[maxm]; int n,k; signed main(){ ios::sync_with_stdio(0); int T; cin>>T; while(T--){ cin>>n>>k; for(int i=1; i<=n; i++)cin>>a[i]; dequema,mi; int ans=0; int l=1; for(int i=1; i<=n; i++){ while(!ma.empty()&&a[ma.back()]a[i])mi.pop_back(); mi.push_back(i); while(!mi.empty()&&!ma.empty()&&a[ma.front()]-a[mi.front()]>=k){ if(ma.front()==l)ma.pop_front(); if(mi.front()==l)mi.pop_front(); l++; } ans+=i-l+1; } cout<

    推荐阅读


    上一篇：django.db.backends.postgresql' isn't an available database backend.解决方法

    下一篇：板子|扩展欧几里得算法证明（exgcd）