P11822 题解

· · 题解

在求解单个问题时，我们采用以下策略：从后往前考虑。对于一个 i，如果其能成为一个分段点（即以其为左端点的段和大于其后面的所有段），那么就直接令其成为分段点。

证明：首先如果不令其成为分段点，那么其余方案的字典序一定会变小。而令其成为分段点时，将左边所有数分成一段一定是个合法方案。

暴力模拟本策略就可以达到 O(n^2) 复杂度，得分 50pts。

直觉地想，向后 push_back 一个数之后，合法方案改变的不会很多（否则重新计算方案对应的答案的时间复杂度就是 O(n^2) 了），且改变的一定是一段后缀。于是我们可以从最后一个数开始，一直使用二分的形式确定下一个分段点。如果有两个新方案的相邻的分段点在旧方案中依然相邻，那么前面的所有分段都不会变，应该停止。如果已经二分到以 0 作为分段点，那么也应该停止。

时间复杂度不会证，但是跑得挺快。赛时在 std::stack 的大常数加持下可以获得 90 分。赛后一把这玩意重写就过了。

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=1e5;

template<class T>
struct Stack{
    int tail=0;
    T in[maxn+5];

    T top(){
        return in[tail];
    }

    bool empty(){
        return tail==0;
    }

    void push(T x){
        in[++tail]=x;
    }

    void pop(){
        tail--;
    }

    int size(){
        return tail;
    }
};

int a[maxn+5],sum[maxn+5];
Stack<pair<int,int>> sta1;
Stack<int> sta2;

bool able(int l,int r,int ge){
    if(l==0){
        return 1;
    }
    return sum[r-1]-sum[l-1]>ge;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    sum[0]=a[0]=1e18;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    sta1.push(make_pair(0,0));
    for(int i=1;i<=n;i++){
        sta2.push(i);
        int lstv=a[i],lstpop=i-1;
        bool nochance=0;
        while(1){
            auto tmp=sta1.top();
            if(!able(tmp.first,sta2.top(),lstv)){
                lstpop=sta1.top().first-1;
                sta1.pop();
                nochance=0;
            }
            else{
                int l=tmp.first,r=lstpop;
                while(l<r){
                    int mid=((l+r)>>1)+1;
                    if(able(mid,sta2.top(),lstv)){
                        l=mid;
                    }
                    else{
                        r=mid-1;
                    }
                }
                if(l==tmp.first){
                    if(nochance||l==0)
                        break;
                    else{
                        lstv=sum[sta2.top()-1]-sum[tmp.first-1];
                        sta2.push(tmp.first);
                        sta1.pop();
                        nochance=1;
                    }
                }
                else{
                    lstv=sum[sta2.top()-1]-sum[l-1];
                    sta2.push(l);
                    nochance=0;
                }
            }
        }
        while(!sta2.empty()){
            sta1.push(make_pair(sta2.top(),sta1.top().second+sta1.size()*sta2.top()));
            sta2.pop();
        }
        cout<<sta1.top().second+(i+1)*sta1.size()<<" ";
    }
}