[ABC282Ex] Min + Sum

一道分治题。比较新的地方在于，别的题都是按中点为M分治，而这道题是按最小值为M分治。记录b的前缀和sum。【L，R】最小值为M，则分为【L，M-1】，【M+1，R】。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+66;
typedef long long ll;
const ll inf=2e18+1;
ll sum[N],s,a[N],b[N],ans,f[23][N];
int n;
ll Q(int l, int r)
{
    int k = __lg(r - l + 1);
    return a[f[k][l]] < a[f[k][r - (1 << k) + 1]] ? f[k][l] : f[k][r - (1 << k) + 1];
}
void solve(int l,int r){
    if(l>r) return;
    int m=Q(l,r);
    solve(l,m-1);solve(m+1,r);
    if(m-l<=r-m){
        for(int i=l;i<=m;i++){
            int j=upper_bound(sum+1,sum+r+1,s+sum[i-1]-a[m])-(sum+1);
            if(j>=m) ans+=j-m+1;
        }
    }else{
        for(int i=m;i<=r;i++){
            int j=lower_bound(sum+l-1,sum+n+1,sum[i]+a[m]-s)-sum+1;
            if(j<=m) ans+=m-j+1;
        }
    }
}
signed main(){
    cin>>n>>s;
    //a[0]=inf;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i],sum[i]=sum[i-1]+b[i];
    for(int i=1;i<=n;i++) f[0][i]=i;
    for (int i = 1; 1 << i <= n; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            f[i][j] = a[f[i - 1][j]] < a[f[i - 1][j + (1 << i - 1)]] ? f[i - 1][j] : f[i - 1][j + (1 << i - 1)];
    solve(1,n);
    cout<<ans;
    return 0;
}