玲珑杯 Round 19 B Buildings （RMQ + 二分）

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].

RMQ+二分

//Round 19 B;

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#define lowbit(x) (x&(-x))

#define max(x,y) (x>y?x:y)

#define min(x,y) (x<y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.141592653589793238462

#define INF 0x3f3f3f3f3f

#define mem(a) (memset(a,0,sizeof(a)))

typedef long long ll;

int maxn[][],minn[][];

int a[];

int n,k,x;

void get_rmq()

{

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

    {

        maxn[i][]=a[i];

        minn[i][]=a[i];

    }

    for(int j=;(<<j)<=n;j++)

    {

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

        {

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

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

        }

    }

}

bool rmq(int l,int r)

{

    if(l>r) return ;

    int f=int(log((double)(r-l+))/log(2.0));

    return max(maxn[l][f],maxn[r-(<<f)+][f])-min(minn[l][f],minn[r-(<<f)+][f])<=k;

}

int main()

{

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

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

    {

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

    }

    get_rmq();

    ll ans=;

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

    {

        int l=,r=i,mid,pos=i;

        while(l<=r)

        {

            mid=(l+r)>>;

            if(rmq(mid,i)) r=mid-,pos=mid;

            else l=mid+;

        }

        ans+=i-pos+;

    }

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

    return ;

}

巴特西

玲珑杯 Round 19 B Buildings （RMQ + 二分）

最新文章

热门文章