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

题意：

给定长度为n的序列a，问有多少个子区间，满足该子区间的最大值和最小值的差值<k

数据范围：n<=1e5，0<=a(i)<=1e9，0<k<=1e9

解法：

设[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数据结构.

解法2:
枚举r,指针维护l,指针向右移动得条件是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<bits/stdc++.h>
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];
        deque<int>ma,mi;
        int ans=0;
        int l=1;
        for(int i=1;i<=n;i++){
            while(!ma.empty()&&a[ma.back()]<a[i])ma.pop_back();
            ma.push_back(i);
            while(!mi.empty()&&a[mi.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<<ans<<endl;
    }
    return 0;
}

本文地址：https://blog.csdn.net/weixin_44178736/article/details/108178720