题解：P14438 [JOISC 2013] 切割蛋糕 / Cake

· · 题解

首先你要断环为链。考虑最小值，你显然不会越过这个位置。故将最小值旋转至 n 即可转化为序列问题。

考虑建出 [1,n-1] 的小根笛卡尔树。每个点的答案对于子树内和子树外分开考虑。这么做是基于一定先取完子树内的再取子树外的。

对于子树内：设 L_{x,i}(2\le x\le m_i) 表示从 L_{x-1,i} 往左数第一个比 a_{L_{x-1,i}} 小的数，并且有且仅有 a_{L_{m_i,i}}<a_i,L_{1,i}=i-1。对于 R_{x,i} 类似的定义。

这样定义有一些好处：

  1. 根据单调栈理论，\sum m_i 是 O(n) 的。
  2. 注意到 (L_{x+1,i},L_{x,i}) 处的值均大于 a_{L_{x,i}}，故取了 L_{x,i} 后就会连续取这一段。也就是说我们可以花费 O(n) 的时间来处理子树内的贡献。

一些细节是 L_{m_i,i} 不在子树内，自然也不会算入贡献。

然后就要考虑子树外：在取完 x 的子树后紧接着就会取自己的父亲。然后取父亲的另一个子树。取另一个子树的过程是从左往右依次取。故可以发现由父亲的答案可以推儿子的答案。于是你递归求值。

记 f_{x,0/1} 表示取完 x 子树外的东西最后先手/后手获得的蛋糕大小。这里的先后手是取完子树后的先后手。从根往下推是简单的。

提交记录。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=3e5+10,M=2e5+10;
mt19937 rnd(time(0));
int n,a[N],Pos=1,ans[N];
vector<int>L[N],R[N];
int s[N][2];
inline int query(int l,int r,int op){return s[r][op]-s[l-1][op];}
int stk[N],top;
int f[N][2],g[N];
int ls[N],rs[N];
void dfs(int x,int l,int r)
{
    ans[x]=g[x]+f[x][(r-l+1)&1];
    if(ls[x])
    {
        f[ls[x]][0]=query(x,r,x&1)+f[x][(r-x+1)&1];
        f[ls[x]][1]=query(x,r,(x&1)^1)+f[x][((r-x+1)&1)^1];
        dfs(ls[x],l,x-1);
    }
    if(rs[x])
    {
        f[rs[x]][0]=query(l,x,x&1)+f[x][(x-l+1)&1];
        f[rs[x]][1]=query(l,x,(x&1)^1)+f[x][((x-l+1)&1)^1];
        dfs(rs[x],x+1,r);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin >> n;
    for ( int i = 1 ; i <= n ; i++ )cin >> a[i];
    for ( int i = 2 ; i <= n ; i++ )if(a[Pos]>a[i])Pos=i;
    rotate(a+1,a+Pos+1,a+1+n);
    for ( int i = 1 ; i <= n ; i++ )s[i][i&1]=a[i];
    for ( int i = 1 ; i <= n ; i++ )s[i][0]+=s[i-1][0],s[i][1]+=s[i-1][1];

    {//solve(n)
        int l=1,r=n-1,op=0;
        ans[n]=a[n];
        while(l<=r)
        {
            if(a[l]>a[r])
            {
                if(op)ans[n]+=a[l];
                l++;
            }else{
                if(op)ans[n]+=a[r];
                r--;
            }
            op^=1;
        }
    }

    int root=0; 
    for ( int i = 1 ; i < n ; i++ )
    {
        while(a[stk[top]]>a[i])L[i].push_back(stk[top--]);
        L[i].push_back(stk[top]);stk[++top]=i;
    }
    stk[top=0]=n;
    for ( int i = n-1 ; i ; i-- )
    {
        while(a[stk[top]]>a[i])R[i].push_back(stk[top--]);
        R[i].push_back(stk[top]);stk[++top]=i;
    }
    for ( int i = 1 ; i < n ; i++ )
    {
        g[i]=a[i];if(n&1)g[i]+=a[n];
        int pl=0,pr=0,op=1;
        while(pl+1<L[i].size()||pr+1<R[i].size())
        {
            if(a[L[i][pl]]>a[R[i][pr]])//这里可以直接如此而保证不越界，原因是 a[L[i].bk()],a[R[i].bk()] 都小于 a[i]，导致对应分支进不去 
            {
                g[i]+=query(L[i][pl+1]+1,L[i][pl],(L[i][pl]&1)^op);
                op^=(L[i][pl]-L[i][pl+1])&1;pl++;
            }else{
                g[i]+=query(R[i][pr],R[i][pr+1]-1,(R[i][pr]&1)^op);
                op^=(R[i][pr+1]-R[i][pr])&1;pr++;
            }
        }
        if(a[L[i].back()]>a[R[i].back()])rs[L[i].back()]=i;
        else if(R[i].back()==n)root=i;
        else ls[R[i].back()]=i;
    }
    dfs(root,1,n-1);

    rotate(ans+1,ans+n+1-Pos,ans+1+n);
    for ( int i = 1 ; i <= n ; i++ )cout << ans[i] << endl;
    return 0;
}