昨天刚做了这个 trick 的板子题，今天竟然又来一道。
涉及到区间 \(\min\) 和计数，一般的方法是比较难做的。所以可以从笛卡尔树和单调栈的角度入手。这题考虑单调栈，固定最小值位置后，就要计算有多少个跨过该位置，并且最小值在该位置上，还满足题目要求的区间。
解决这个问题可以考虑用单调栈处理出左右第一个比它小的数，然后枚举其中一侧，另一侧用二分找到可行区间。问题就在于应该怎么枚举。我们先猜测每次都枚举更短的那一侧是正确的。交上去，发现过了。
下面浅浅证明一下：设 \(T(n)\) 为序列长度为 \(n\) 时的复杂度。则有 \(T(n)=\max\limits_{2\times x\le n} (T(x)+T(n-x)+O(x))\)。容易发现，每个位置如果产生了一次贡献，则它所在的区间长度至少减半，所以每个位置最多产生 \(O(\log n)\) 次贡献。所以复杂度为 \(O(n\log n)\)，再加上二分的复杂度，总复杂度即为 \(O(n\log^2n)\)。
还有一个在这种单调栈处理中常用的技巧：当遇到重复数字又不想算重时，可以考虑一边取等，一边不取的做法，具体可以参考代码。
code：
点击查看代码
int n,top,b[N],st[N],f[N],g[N];
ll m,a[N],s[N];
void Yorushika(){
scanf("%d%lld",&n,&m);
rep(i,1,n)scanf("%lld",&a[i]);
rep(i,1,n)scanf("%d",&b[i]),s[i]=s[i-1]+b[i];
a[0]=a[n+1]=-1;
rep(i,1,n+1){
while(top&&a[st[top]]>=a[i])f[st[top--]]=i;
st[++top]=i;
}
top=0;
drep(i,n,0){
while(top&&a[st[top]]>a[i])g[st[top--]]=i;
st[++top]=i;
}
ll ans=0;
rep(i,1,n){
if(i-g[i]<=f[i]-i){
rep(j,g[i],i-1){
ll x=m+s[j]-a[i];
int p=upper_bound(s,s+n+1,x)-s-1;
if(p<i)continue;
p=min(p,f[i]-1);
ans+=p-i+1;
}
}else{
rep(j,i,f[i]-1){
ll x=s[j]+a[i]-m;
int p=lower_bound(s,s+n+1,x)-s;
if(p>=i)continue;
p=max(p,g[i]);
ans+=i-p;
}
}
}
printf("%lld\n",ans);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}