# f816 TOI_Youtube

###### tags: `競程題解`,`競程`

Timestamp:2023/03/04 09:45

心得：想了好久 窩好笨QQ

想法：
對 d 做前綴和，對於一個 v_i 一定會有一個被刪掉的時候 它在 被加入~被刪掉(被扣到小於0) 這段期間，一定會被扣掉這段期間的所有 d

所以我把它變成差分的形式 在我把這個數加入的時候，記錄一個 cnt_j 代表目前在算到 j 的時候所有不小於 0 且大於 d_j 的數 (就可以直接扣掉 cnt_j * d_j)

那如果目前這個數介於 0~d_j 之間呢 那麼這個數對於 ans_ｊ的貢獻就直接是 0 就好 但不是每一個 v_i 扣到最後都會剛剛好是 0

所以要在差分那邊動一點手腳 直接在差分的時候直接扣掉就好。

應該看扣就知道了~

#include "iostream"
using namespace std;
#define int long long
int ans[400010]={},cnt[400010]={};
int pre[400010]={},ary[400010]={},bonu[400010]={};
int n;
int sum(int l,int r){return pre[r]-pre[l-1];}
void fd(int pos){
    int l = pos+1;
    int r = l;
    int add = (1<<30);
    while(add){
        if(r+add>n+1){
            add/=2;
            continue;
        }
        if(sum(l,r+add)>ary[pos]){
            add/=2;
        }
        else{
            r+=add;
        }
    }
    // r -> max pos (full)
    if(r==l&&ary[pos]<=sum(r,r)){
        return ;
    }
    cnt[l]++;
    cnt[r+1]--;
    ans[l]+=ary[pos];
    ans[r+1]-=ary[pos]-sum(l,r);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    int k,s;
    for(int i=1;i<=n;i++){
        cin>>ary[i]>>s;
        pre[i]=pre[i-1]+s;
    }
    pre[n+1]=pre[n];
    for(int i=1;i<=n;i++)fd(i);
    int now=0,ct=0;
    for(int i=1;i<=n;i++){
        now+=ans[i];
        ct+=cnt[i];
        now-=ct*sum(i,i);
        cout<<now+bonu[i]+ary[i]<<"\n";
    }
}