补题 | CF2242F

题目

While reading the statement of this problem, we recommend forgetting that summer consists of ​92 days and that a day consists of ​1440 minutes. This is Berland, and things are different here.

Monocarp is a student at a provincial university in Berland. The summer holidays have just begun, and they will last for the next ​n days. Monocarp has long dreamed of going to the capital of Berland, so he will choose one day ​i among these days, arrive in the capital on that day, and spend the rest of the holidays there.

The capital of Berland is not a very cheap city, and Monocarp has ​0 Berland dollars with him. Naturally, this is not enough to visit interesting places and buy souvenirs. Therefore, on some days in the capital, Monocarp will work as a freelancer. He does not want to work in his hometown, since he has already spent the whole academic year doing university assignments.

Formally, on the ​i-th day of the holidays, Monocarp will have ​a_i free minutes, which he will spend either working or resting and buying souvenirs. If Monocarp has at least ​a_i dollars at the beginning of the ​i-th day, then on that day he will spend them on rest and souvenirs at a rate of ​1 dollar per minute; that is, during this day, he will spend ​a_i dollars. Otherwise, he will spend this time working, earning ​1 dollar per minute; that is, during this day, he will earn ​a_i dollars. Note that Monocarp always makes his decision for the entire day; it is impossible for him to both spend and earn money during the same day.

Your task is to determine, for each number of days ​k from ​1 to ​n, how many dollars Monocarp will have left after the last day of the holidays if he lives in the capital for exactly ​k last days (i. e. if he arrives on the day ​(n-k+1)).

做法

对于每一天不妨将其写成分段函数的形式：

考虑停留两天的情况，答案即 ​f_{a_n}(a_{n-1}) ，可将两天整合成一个函数：

又由题知当前手中的钱不可能大于等于 ​2n ，可以使用 ​dp[m] 记录当剩余 ​m 元后经历剩余假期后手上还剩余的金钱，考虑手上有 ​m 元，加入新的一天 ​x ，显然有：

又知道 ​m \in [0,2n) ，那么当 ​m<x 时，​m+x 只会落在 ​[x,2x) ；当 ​m\ge x 时，​m-x 只会落在 ​[0,2n-x) ，因此对于 ​dp 的迭代即把这两段拼起来，易知新的长度依旧为 ​2n .

官方的 treap 实现有点难，这里提供一个分块实现的思路，我们用若干连续段表示当前 ​dp 序列。每次转移只需要取出当前序列中的两个区间并拼接，扫描所有段即可完成。为防止段数过多，当段数超过阈值时，将序列展开并重新分块。设当前段数为 ​K，单次转移为 ​O(K)，重构为 ​O(n)。由于段数被限制在常数阈值附近，实际运行复杂度接近 ​O(n\sqrt n) 或 ​O(n\cdot B)，空间复杂度 ​O(n)。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{
    int l,r;
};

const int S=700;
const int LIM=2600;

vector<int> base,tmp,ans;
vector<node> seg,L,R;

void add(vector<node>& v,int l,int r){
    if(l>=r) return;
    if(!v.empty()&&v.back().r==l) v.back().r=r;
    else v.push_back({l,r});
}

void rebuild(int m){
    tmp.clear();
    tmp.reserve(m);
    for(auto p:seg){
        for(int i=p.l;i<p.r;i++) tmp.push_back(base[i]);
    }
    base.swap(tmp);
    seg.clear();
    for(int i=0;i<m;i+=S){
        seg.push_back({i,min(i+S,m)});
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    int m=2*n;
    base.resize(m);
    ans.resize(n+1);

    for(int i=0;i<m;i++) base[i]=i;

    for(int i=0;i<m;i+=S){
        seg.push_back({i,min(i+S,m)});
    }

    for(int i=n;i>=1;i--){
        int x=a[i];

        L.clear();
        R.clear();
        L.reserve(seg.size()+5);
        R.reserve(seg.size()+5);

        int cur=0;
        for(auto p:seg){
            int len=p.r-p.l;
            int nxt=cur+len;

            int l=max(cur,x);
            int r=min(nxt,2*x);
            if(l<r) add(L,p.l+l-cur,p.l+r-cur);

            l=cur;
            r=min(nxt,m-x);
            if(l<r) add(R,p.l+l-cur,p.l+r-cur);

            cur=nxt;
        }

        seg.clear();
        seg.reserve(L.size()+R.size()+5);

        for(auto p:L) add(seg,p.l,p.r);
        for(auto p:R) add(seg,p.l,p.r);

        ans[n-i+1]=base[seg[0].l];

        if((int)seg.size()>LIM) rebuild(m);
    }

    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" \n"[i==n];
    }

    return 0;
}