连续非空子序列

先求一遍前缀和数组为h
需要求满足 && 的式子
题目就转为求前缀和数组中逆序对的数目
使用归并排序求逆序对
或使用高级数据结构维护（如平衡树）

参考代码（归并排序）

#include<bits/stdc++.h>
using namespace std;
long long n;
long long h[1000008]; 
long long a[1000008];
long long c[1000008];
long long ans;
void fsort(long long l,long long r)
{
    if(l>=r) return ;
    long long tot=0;
    long long mid=(l+r)/2;
    long long aa=l,bb=mid+1;
    fsort(l,mid);
    fsort(mid+1,r);
    while(aa<=mid&&bb<=r){
        if(a[aa]<a[bb]){
            c[++tot]=a[aa++];
            ans+=(r-bb+1);
        }
        else{
            c[++tot]=a[bb++];
        }
    }
    while(aa<=mid)
        c[++tot]=a[aa++];
    while(bb<=r)
        c[++tot]=a[bb++];
    for(long long i=l,j=1;i<=r;i++,j++)
        a[i]=c[j];
}
int main()
{
    scanf("%lld",&n);
    a[1]=h[1]=0;
    n++;
    for(long long i=2;i<=n;i++){
        scanf("%lld",&h[i]);
        a[i]=a[i-1]+h[i];
    }
    fsort(1,n);
    cout<<ans<<"\n";
    return 0;
}

参考代码（Splay树）

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define inf INT_MAX
#define lc(x) s[x].ch[0]
#define rc(x) s[x].ch[1]
using namespace std;
const int N=1e6+10;
int n,rt,tot;
int a[N];
struct nkl {
    int ch[2],siz,cnt,val,fa;
} s[N];
inline int ident(int x,int y) {
    return (rc(y)==x);
}
inline void cn(int x,int y,int k) {
    s[x].fa=y;
    s[y].ch[k]=x;
}
inline void upd(int x) {
    s[x].siz=s[lc(x)].siz+s[rc(x)].siz+s[lc(x)].cnt+s[rc(x)].cnt;
}
inline void rotate(int x) {
    int y=s[x].fa,z=s[y].fa,k=ident(x,y);
    cn(s[x].ch[k^1],y,k);
    cn(x,z,ident(y,z));
    cn(y,x,k^1);
    upd(y),upd(x);
}
inline void splay(int x,int to) {
    if(!to) rt=x;
    while(s[x].fa!=to) {
        int y=s[x].fa,z=s[y].fa;
        if(z!=to)
            ident(x,y)^ident(y,z) ? rotate(x):rotate(y);
        rotate(x);
    }
}
inline void newcode(int &now,int x,int fa) {
    now=++tot;
    s[now].val=x;
    s[now].fa=fa;
    s[now].cnt++;
}
inline void ins(int &now,int x,int fa) {
    if(!now) newcode(now,x,fa),splay(now,0);
    else if(s[now].val<x) ins(s[now].ch[1],x,now);
    else if(s[now].val>x) ins(s[now].ch[0],x,now);
    else s[now].cnt++,splay(now,0);
}
signed main() {
    scanf("%lld",&n);
    for (int i=1; i<=n; i++)
        scanf("%lld",&a[i]),a[i]+=a[i-1];
    ll ans=0;
    for (int i=1; i<=n; i++) {
        ins(rt,a[i],0);
        ans+=s[lc(rt)].siz+s[lc(rt)].cnt;
        if(a[i]>0) ans++;
    }
    printf("%lld\n",ans);
    return 0;
}