牛客练习赛97 E

一个结论是一段区间可行当且仅当其总石子个数是偶数且最多者不超过总数一半。

笛卡尔树上启发式合并即可。

（听说数据水，乱搞也能过。）

// 笛卡尔树毁我青春
// 隐式构建.jpg
ullt S[100005];
uint Cnt[2][100005];
uint A[100005];
struct Seg
{
    uint len;uint v;Seg*L,*R;
    Seg(uint*Bgn,uint*End):L(NULL),R(NULL){if((len=End-Bgn)>1)L=new Seg(Bgn,Bgn+(len>>1)),R=new Seg(Bgn+(len>>1),End),v=std::max(L->v,R->v);else v=*Bgn;}
    uint find(uint l,uint r)
    {
        if(!l&&r==len)return v;
        if(l<(len>>1))
            if(r<=(len>>1))return L->find(l,r);
            else return std::max(L->find(l,len>>1),R->find(0,r-(len>>1)));
        else return R->find(l-(len>>1),r-(len>>1));
    }
};
int main()
{
    ullt ans=0;uint n;scanf("%u",&n);
    for(uint i=0;i<n;i++)scanf("%u",A+i),S[i+1]=S[i]+A[i];
    for(uint i=0;i<=n;i++)Cnt[S[i]&1][i+1]++,Cnt[0][i+1]+=Cnt[0][i],Cnt[1][i+1]+=Cnt[1][i];
    Seg T(A,A+n);
    for(uint i=0;i<n;i++)
    {
        uint l=0,r=i;
        while(l<r){uint mid=(l+r)>>1;if(T.find(mid,i)>A[i])l=mid+1;else r=mid;}
        uint L=l;
        l=i+1,r=n;
        while(l<r){uint mid=(l+r+1)>>1;if(T.find(i+1,mid)>=A[i])r=mid-1;else l=mid;}
        uint R=l;
        if(i-L>R-i)
        {
            for(uint j=i+1;j<=R;j++)
            {
                l=L,r=i+1;
                while(l<r)
                {
                    uint mid=(l+r)>>1;
                    if(S[j]-S[mid]<A[i]*2)r=mid;
                    else l=mid+1;
                }
                ans+=Cnt[S[j]&1][l]-Cnt[S[j]&1][L];
            }
        }
        else{
            for(uint j=L;j<=i;j++)
            {
                l=i+1,r=R+1;
                while(l<r)
                {
                    uint mid=(l+r)>>1;
                    if(S[mid]-S[j]<A[i]*2)l=mid+1;
                    else r=mid;
                }
                ans+=Cnt[S[j]&1][R+1]-Cnt[S[j]&1][l];
            }
        }
    }
    printf("%llu\n",ans);
	return 0;
}