启发式分治

题解

启发式分治是为了解决序列上的一类特殊分治问题，一般的分治每次将区间的中点作为划分点将区间划分成两部分递归下去，而此类特殊分支问题的划分点选取与问题的要求有关，无法自行规定，所以对于每一次分治$(l,r)$进行处理的复杂度也不能高达$O(r-l+1)$，否则整个问题的复杂度将会退化为$O(n^2)$。

举例说明：设整个序列$(a_i>=0)$的权值为$good$的区间个数，设区间$good$当且仅当区间最大值的两倍大于等于区间和。

此时问题可以用从大到小枚举最大值并划分区间来解决，进而推得利用分治进行解决，对于每个分治的区间$(l,r)$，首先找到最大值的位置$p$，那么满足条件的子区间$(L,R)$一定满足$L<=p<=R$。所以我们可以枚举$L$的位置，然后在前缀和中二分出满足条件的$R$的最小位置，再将分治为$(l,p-1),(p+1,r)$两个子区间进行处理，做到单次分治$O((p-l+1)logn)$的时间复杂度，但这样整体复杂度会退化到$O(n^2logn)$。所以我们利用启发式的思想考虑问题，容易发现在枚举那一步时不一定要枚举$L$的位置，也可以结合枚举$R$的位置二分$L$做到单次分治$O(min(p-l+1,r-p)logn)$的复杂度，从而做到$O(nlogn)$的整体复杂度（一共调用分支函数$n$次而不是$nlogn$次，因为划分点不会在区间分治后得到的两个子区间中出现）。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+5;

int Case;
int n,a[N];
ll ans,b[N];

struct ST{
    int tot;
    int ls[N<<1],rs[N<<1],mx[N<<1];
    
    void up(int x){
    }
    
    int build(int l,int r){
        int x=++tot;
        if(l==r){
            mx[x]=l;
            return x;
        }
        int mid=l+r>>1;
        ls[x]=build(l,mid);
        rs[x]=build(mid+1,r);
        if(a[mx[ls[x]]]>a[mx[rs[x]]])mx[x]=mx[ls[x]];
        else mx[x]=mx[rs[x]];
        return x;
    }
    
    int getmx(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R)return mx[x];
        int mid=l+r>>1;
        if(R<=mid)return getmx(ls[x],l,mid,L,R);
        if(L>mid)return getmx(rs[x],mid+1,r,L,R);
        int ret1=getmx(ls[x],l,mid,L,R);
        int ret2=getmx(rs[x],mid+1,r,L,R);
        return a[ret1]>a[ret2]?ret1:ret2;
    }
    
    void init(){
        for(int i=1;i<=tot;++i){
            mx[i]=0;
            ls[i]=rs[i]=0;
        }
        tot=0;
        int rt=build(1,n);
    }
}T;

void Solve(int l,int r){
    if(l>=r)return;
    int p=T.getmx(1,1,n,l,r);
    int mid=l+r>>1;
    if(p<=mid){
        for(int i=l-1;i<=p-1;++i){
            int pos=lower_bound(b+p,b+r+1,b[i]+a[p]*2)-b;
            ans+=(r-pos+1);
        }
    }
    else{
        for(int i=p;i<=r;++i){
            int pos=upper_bound(b+l-1,b+p,b[i]-a[p]*2)-b-1;
            ans+=(pos-l+2);
        }
    }
    Solve(l,p-1);
    Solve(p+1,r);
}

int main(){
    scanf("%d",&Case);
    while(Case--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            b[i]=b[i-1]+a[i];
        }
        T.init();
        ans=0;
        Solve(1,n);
        printf("%lld\n",ans);
    }
}