玲珑杯”ACM比赛 Round #19 B 维护单调栈

1149 - Buildings

Time Limit：2s Memory Limit：128MByte

Submissions：588Solved：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].

题意：给你一个长度为n的序列问有多少区间使得区间最大值-区间最小值<=k

题解：单调栈处理出以a[i]为最小值的区间左界右界组合出合法的区间注意（同一左界右界)或者称为同一块下的最小值可能会有重复

从左向右遍历时将当前值的左界改为(同一块中上一个相同值的位置+1) 具体看代码;

 #pragma comment(linker, "/STACK:102400000,102400000")

 #include <cstdio>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <cctype>

 #include <map>

 #include <set>

 #include <queue>

 #include <bitset>

 #include <string>

 #include <complex>

 #define ll long long

 #define mod 1000000007

 using namespace std;

 ll n,k;

 ll a[];

 ll l[],r[];

 map<ll,map<ll,ll>> mp;

 int main()

 {

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

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

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

         a[]=-1ll;

         a[n+]=-1ll;

         l[]=1ll;

         for(int i=; i<=n; i++) //关键********

         {

             ll temp=i-;

             while(a[temp]>=a[i])//维护一个递增的序列

                 temp=l[temp]-;

             l[i]=temp+;

         }

         r[n]=n;

         for (int i=n-; i>=; i--)

         {

             ll temp=i+;

             while(a[temp]>=a[i])

                 temp=r[temp]+;

             r[i]=temp-;

         }

         ll ans=;

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

         {

             ll x=,y=;

             if(mp[l[i]][r[i]]!=){//去重 更改l[i]

               ll now=l[i];

               l[i]=mp[l[i]][r[i]];

               mp[now][r[i]]=i+;

              }

              else

             mp[l[i]][r[i]]=i+;

             for(int j=i-; j>=l[i]; j--)

             {

                 if((a[j]-a[i])<=k)

                     x++;

                 else

                     break;

             }

             for(int j=i+; j<=r[i]; j++)

             {

                 if((a[j]-a[i])<=k)

                     y++;

                 else

                     break;

             }

             ans=ans+x*y+x+y+1ll;

         }

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

     return ;

 }

巴特西

玲珑杯”ACM比赛 Round #19 B 维护单调栈

最新文章

热门文章