2019牛客多校第三场 Removing Stones

题意

给出一个序列，问有多少个区间满足：最大值的两倍小于等于区间和

题解

分治的思想，也是笛卡尔树
对于所有的最大值，看多少个包含它的区间满足要求
先在区间 $[1, n]$ 中找到最大值的下标 $k$
如果左区间长度较小，我们则枚举左端点在左区间的，在右区间二分找到合适的右端点
如果右区间长度较小，则枚举右端点在右区间
总复杂度为 $O (n \cdot l o g^{2} n)$
注意用 $l o w e r_b o u n d$ 时的边界条件

代码

#include<bits/stdc++.h>
#define N 300010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
#define mod 97
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%dd",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;

int a[N],lg[N];
LL s[N],ans;
int f[N][19];

inline int idx(int l,int r){
    int t=lg[r-l];
    if (a[f[l][t]]>a[f[r-(1<<t)+1][t]])
        return f[l][t];else
        return f[r-(1<<t)+1][t];
}

void work(int l,int r){
    if (l>=r) return;
    if (l+1==r){
        if (a[l]==a[r]) ans++;
        return;
    }
    int k=idx(l,r),t;LL M=a[k],tm=0,la;
    if (k-l>r-k){
        for(int i=k;i<=r;i++){
            tm+=a[i]; la=M*2-tm;
            if (s[i]-s[l-1]<M*2) continue;
            if(la<=0) t=k;else {
                t=lb(s+l,s+k+1,s[k-1]-la)-s;
                if (la==s[k-1]-s[t]) t++;
            }
            ans+=t-l+1;
        }
    }else{
        for(int i=k;i>=l;i--){
            tm+=a[i]; la=M*2-tm;
            if (s[r]-s[i-1]<M*2) continue;
            if (la<=0) t=k;else 
                t=lb(s+k,s+r+1,s[k]+la)-s;
            ans+=r-t+1;
        }
    }
    work(l,k-1);
    work(k+1,r);
}

int main(){
    for(int i=1;(1<<i)<N;i++) lg[1<<i]=1;
    for(int i=1;i<N;i++) lg[i]+=lg[i-1];
    int T;
    sc(T);    
    while(T--){
        int n;
        sc(n);
        for(int i=1;i<=n;i++) sc(a[i]),s[i]=s[i-1]+a[i],f[i][0]=i;

        for(int j=1;(1<<j)<=n;j++)
            for(int i=1;i<=n;i++) if (i+(1<<j)-1<=n)
                if (a[f[i][j-1]]>a[f[i+(1<<j-1)][j-1]])
                    f[i][j]=f[i][j-1];else
                    f[i][j]=f[i+(1<<j-1)][j-1];

        ans=0;
        work(1,n);
        printf("%lld\n",ans);
    }
}