前置知识
树状数组 | 序列分治
解法
考虑序列分治，设因 \(\max\) 和 \(\min\) 形成的分节点先后为 \(k_{1},k_{2}\)。
对于 \(j \in (mid,k_{1}]\)，等价于统计满足 \(\max\limits_{h=i}^{mid} \{ a_{h} \}-\min\limits_{h=i}^{mid} \{ a_{h} \} \le j-i+k\) 的 \(j\) 的数量，容易求解。
对于 \(j \in (k_{1},k_{2}]\)，以 \([i,j]\) 的 \(\max\) 落在 \((k_{1},k_{2}]\) 为例，需要统计满足 \(\max\limits_{h=mid+1}^{j} \{ a_{h} \}-\min\limits_{h=i}^{mid} \{ a_{h} \} \le j-i+k\) 的 \(j\) 数量，移项得到 \(\max\limits_{h=mid+1}^{j} \{ a_{h} \}-j \le \min\limits_{h=i}^{mid} \{ a_{h} \}-i+k\)，移动指针的过程中树状数组维护 \(\max\limits_{h=mid+1}^{j} \{ a_{h} \}-j\) 的桶数组即可。
对于 \(j \in (k_{2},r]\)，需要统计 \(\max\limits_{h=mid+1}^{j} \{ a_{h} \}-\min\limits_{h=mid+1}^{j} \{ a_{h} \} \le j-i+k\) 的 \(j\) 数量，移项得到 \(\max\limits_{h=mid+1}^{j} \{ a_{h} \}-\min\limits_{h=mid+1}^{j} \{ a_{h} \}-j \le -i+k\)，移动指针的过程中树状数组维护 \(\max\limits_{h=mid+1}^{j} \{ a_{h} \}-\min\limits_{h=mid+1}^{j} \{ a_{h} \}-j\) 的桶数组即可。
注意下标移位。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
int a[140010],pre_max[140010],pre_min[140010],n,m;
ll ans=0;
struct BIT
{
int c[500010];
int lowbit(int x)
{
return (x&(-x));
}
void add(int n,int x,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
{
c[i]+=val;
}
}
void del(int n,int x)
{
for(int i=x;i<=n;i+=lowbit(i))
{
c[i]=0;
}
}
int getsum(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
{
ans+=c[i];
}
return ans;
}
}T[3];
void solve(int l,int r)
{
if(l==r)
{
ans++;
return;
}
int mid=(l+r)/2,suf_max=0,suf_min=0x7f7f7f7f;
pre_max[mid+1]=pre_min[mid+1]=a[mid+1];
for(int i=mid+2;i<=r;i++)
{
pre_max[i]=max(pre_max[i-1],a[i]); pre_min[i]=min(pre_min[i-1],a[i]);
}
for(int i=mid+1;i<=r;i++) T[0].add(500000,pre_max[i]-pre_min[i]-i+300000,1);
for(int i=mid,k1=mid,k2=mid;i>=l;i--)
{
suf_max=max(suf_max,a[i]); suf_min=min(suf_min,a[i]);
while(k1+1<=r&&suf_max>=pre_max[k1+1]&&suf_min<=pre_min[k1+1])
{
k1++;
T[1].add(500000,pre_max[k1]-k1+300000,-1);
T[2].add(500000,-k1-pre_min[k1]+300000,-1);
}
while(k2+1<=r&&(suf_max>=pre_max[k2+1]||suf_min<=pre_min[k2+1]))
{
k2++;
T[0].add(500000,pre_max[k2]-pre_min[k2]-k2+300000,-1);
T[1].add(500000,pre_max[k2]-k2+300000,1);
T[2].add(500000,-k2-pre_min[k2]+300000,1);
}
ans+=max(0,k1-max(mid+1,suf_max-suf_min-m+i)+1);
ans+=T[0].getsum(m-i+300000);
ans+=(suf_min<=pre_min[k2])?T[1].getsum(suf_min-i+m+300000):T[2].getsum(-suf_max-i+m+300000);
}
for(int i=mid+1;i<=r;i++) T[0].del(500000,pre_max[i]-pre_min[i]-i+300000);
for(int i=mid+1;i<=r;i++) T[1].del(500000,pre_max[i]-i+300000);
for(int i=mid+1;i<=r;i++) T[2].del(500000,-i-pre_min[i]+300000);
solve(l,mid);
solve(mid+1,r);
}
int main()
{
// #define Isaac
#ifdef Isaac
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
solve(1,n);
cout<<ans<<endl;
return 0;
}