补题 | 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
题目#
While reading the statement of this problem, we recommend forgetting that summer consists of days and that a day consists of 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 days. Monocarp has long dreamed of going to the capital of Berland, so he will choose one day 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 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 -th day of the holidays, Monocarp will have free minutes, which he will spend either working or resting and buying souvenirs. If Monocarp has at least dollars at the beginning of the -th day, then on that day he will spend them on rest and souvenirs at a rate of dollar per minute; that is, during this day, he will spend dollars. Otherwise, he will spend this time working, earning dollar per minute; that is, during this day, he will earn 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 from to , how many dollars Monocarp will have left after the last day of the holidays if he lives in the capital for exactly last days (i. e. if he arrives on the day ).
做法#
对于每一天不妨将其写成分段函数的形式:
考虑停留两天的情况,答案即 ,可将两天整合成一个函数:
又由题知当前手中的钱不可能大于等于 ,可以使用 记录当剩余 元后经历剩余假期后手上还剩余的金钱,考虑手上有 元,加入新的一天 ,显然有:
又知道 ,那么当 时, 只会落在 ;当 时, 只会落在 ,因此对于 的迭代即把这两段拼起来,易知新的长度依旧为 .
官方的 treap 实现有点难,这里提供一个分块实现的思路,我们用若干连续段表示当前 序列。每次转移只需要取出当前序列中的两个区间并拼接,扫描所有段即可完成。为防止段数过多,当段数超过阈值时,将序列展开并重新分块。设当前段数为 ,单次转移为 ,重构为 。由于段数被限制在常数阈值附近,实际运行复杂度接近 或 ,空间复杂度 。
代码#
#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;
}cpp