“玲珑杯”ACM比赛 Round #19 B -- Buildings （RMQ + 二分）

“玲珑杯”ACM比赛 Round #19

Start Time：2017-07-29 14:00:00 End Time：2017-07-29 16:30:00 Refresh Time：2017-07-29 16:42:55 Private

B -- Buildings

Time Limit：2s Memory Limit：128MByte

Submissions：590Solved：151

DESCRIPTION

There are nn buildings lined up, and the height of the ii-th house is hihi.

An inteval [l,r][l,r](l≤r)(l≤r) is harmonious if and only if max(hl,…,hr)−min(hl,…,hr)≤kmax(hl,…,hr)−min(hl,…,hr)≤k.

Now you need to calculate the number of harmonious intevals.

INPUT

The first line contains two integers n(1≤n≤2×105),k(0≤k≤109)n(1≤n≤2×105),k(0≤k≤109). The second line contains nn integers hi(1≤hi≤109)hi(1≤hi≤109).

OUTPUT

Print a line of one number which means the answer.

SAMPLE INPUT

3 1 1 2 3

SAMPLE OUTPUT

HINT

Harmonious intervals are: [1,1],[2,2],[3,3],[1,2],[2,3][1,1],[2,2],[3,3],[1,2],[2,3].

【题意】给你一个序列，然后问你有多少个区间的最大值-最小值<=k。

【分析】我们可以用RMQ来logn查询区间最大、最小值，然后枚举每一位最为区间右端点，向左二分左端点，将区间长度加到ans即可。

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

#define mp make_pair

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 2e5+;

const int mod = 1e9+;

const double pi= acos(-1.0);

typedef pair<int,int>pii;

int n,k;

int a[N];

int mn[N][],mx[N][],mm[N];

void init() {

    for(int j=; j<=mm[n]; ++j) {

        for(int i=; i+(<<j)-<=n; ++i) {

            mn[i][j]=min(mn[i][j-],mn[i+(<<(j-))][j-]);

            mx[i][j]=max(mx[i][j-],mx[i+(<<(j-))][j-]);

        }

    }

}

int getmx(int l,int r) {

    int k = mm[r-l+];

    return max(mx[l][k],mx[r-(<<k)+][k]);

}

int getmn(int l,int r) {

    int k = mm[r-l+];

    return min(mn[l][k],mn[r-(<<k)+][k]);

}

int main(){

    mm[]=-;

    for(int i=; i<N; ++i)mm[i]=(i&(i-))?mm[i-]:mm[i-]+;

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++){

        scanf("%d",&a[i]);

        mn[i][]=mx[i][]=a[i];

    }

    init();

    int l,r,res;

    ll ans=;

    for(int i=;i<=n;i++){

        l=;r=i;res=i;

        while(l<=r){

            int mid=(l+r)/;

            int maxn=getmx(mid,i);

            int minn=getmn(mid,i);

            if(maxn-minn>k)l=mid+;

            else r=mid-,res=mid;

        }

        ans+=i-res+;

    }

    printf("%lld\n",ans);

    return ;

}

巴特西

“玲珑杯”ACM比赛 Round #19 B -- Buildings （RMQ + 二分）

最新文章

热门文章