题解 | #玛卡巴卡玩游戏#

首先我们需要讨论一堆石子序列能否消完的充要条件，显然有：当且仅当序列最大值小于等于石子总数一半且石子总数为偶数时，石子序列可消完 。这个可以用每次消最多的石子堆和旁边的石子堆来感性理解，证明不难。

接下来我们考虑分治求解。对于一个分治区间 $[l, r]$ ,枚举答案区间右端点 $R$ $( mid < R \le r )$ 考虑有哪些答案区间左端点 $L$ $(l \le L \le mid)$ 满足条件。我们可以在从 $m i d + 1$ 开始向右枚举 $R$ 同时维护一个指针 $p o s$ $( l \le pos \le mid)$ 使得 $[p o s, m i d]$ 的最大值小于等于 $[m i d + 1, R]$ 的最大值，而 $a_{pos}$ 大于 $[m i d + 1, R]$ 的最大值。这样对于 $pos \le L \le mid$ 的 $L$ 答案序列的最大值就是 $[m i d + 1, R]$ 的最大值，而对于 $l \le L < pos$ 的 $L$ 答案序列最大值就是 $[L, m i d]$ 的最大值。对于前者，我们可以开两个桶记录 $L \in [pos,mid]$ 里 $\sum_{L}^{mid} a_i$ 为奇/偶的 $L$ 个数，同时要满足 $\sum_{mid+1}^R a_i - 2 \times maxn \ge -\sum_{L}^{mid} a_i$ （注意到单调性，可以二分求 $L$ 的取值区间）；对于后者，我们可以维护离散化后的树状数组，满足 $l \le L < pos$ 且 $\sum_{L}^{mid} a_i - 2 \times maxn \ge -\sum_{mid+1}^R a_i$ ，一开始时把第二个限制里左边式子值全丢进去，每次向左移 $p o s$ 时删去即可。

时间复杂度是 $O (n l o g^{2} n)$ 。

参考代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
#define fi first
#define sc second
using namespace std;
typedef long long ll;
const int N=1e5+5,M=45,oo=1e9;
int n,a[N];
inline int read() {
    int x=0,flag=0;char ch=getchar();
    while(ch<'0'||ch>'9') {flag|=(ch=='-');ch=getchar();}
    while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return flag?-x:x;
}
inline int mx(int x,int y) {return x>y?x:y;}
inline int mn(int x,int y) {return x<y?x:y;}
inline ll mxl(ll  x,ll  y) {return x>y?x:y;}
inline ll mnl(ll  x,ll  y) {return x<y?x:y;}
inline void swp(int &x,int &y) {x^=y^=x^=y;}
inline int as(int x) {return x>0?x:-x;}
int maxn[N],t[N][2];
ll sum[N],ans,b[N];
inline int Pos(int l,int r,ll S) {
    int mid=(l+r)>>1;
    while(l<=r) {
        mid=(l+r)>>1;
        if(sum[mid]+S>=0) l=mid+1;
        else r=mid-1;
    }
    return r;
}
namespace Bit {
    int w[N][2],lim;
    inline void add(int x,int id,int val) {
        while(x<=lim) {
            w[x][id]+=val;
            x+=x&-x;
        }
    }
    inline int query(int x,int id) {
        int sum=0;
        while(x) {
            sum+=w[x][id];
            x-=x&-x;
        }
        return sum;
    }
}using namespace Bit;
inline int lower(ll val) {return lower_bound(b+1,b+lim+1,val)-b;}
void solve(int l,int r) {
    if(l==r) {
        return ;
    }
    int mid=(l+r)>>1,len=0;
    maxn[mid]=a[mid]; sum[mid]=a[mid]; b[++len]=sum[mid]-2ll*maxn[mid];
    for(int i=mid-1;i>=l;--i) maxn[i]=mx(maxn[i+1],a[i]),sum[i]=sum[i+1]+a[i],b[++len]=sum[i]-2ll*maxn[i];
    sort(b+1,b+len+1); len=unique(b+1,b+len+1)-b-1;
    lim=len; t[mid+1][0]=t[mid+1][1]=0;
    for(int i=mid;i>=l;--i) {
        t[i][0]=t[i+1][0]; t[i][1]=t[i+1][1];
        add(len-lower(sum[i]-2ll*maxn[i])+1,sum[i]&1,1),t[i][sum[i]&1]++;
    }
    int pos=mid;
    for(int i=mid+1;i<=r;++i) {
        if(i==mid+1) maxn[i]=a[mid+1],sum[i]=a[i];
        else maxn[i]=mx(maxn[i-1],a[i]),sum[i]=sum[i-1]+a[i];
        while(pos>=l&&maxn[pos]<=maxn[i]) {add(len-lower(sum[pos]-2ll*maxn[pos])+1,sum[pos]&1,-1);--pos;}
      
        int wos=Pos(l,mid,sum[i]-2ll*maxn[i]);
        ans+=(wos+1>=pos+1?t[pos+1][sum[i]&1]-t[wos+1][sum[i]&1]:0);
      
        wos=lower_bound(b+1,b+len+1,-sum[i])-b;
        ans+=query(len-wos+1,sum[i]&1);
    }
    while(pos>=l) {add(len-lower(sum[pos]-2ll*maxn[pos])+1,sum[pos]&1,-1);--pos;}
    for(int i=l;i<=mid;++i) t[i][0]=t[i][1]=0;
    solve(l,mid); solve(mid+1,r);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    solve(1,n);
    printf("%lld\n",ans);
    return 0;
}