题解：P11861 [CCC 2025 Senior] 写作业 / To-Do List

ELECTRODE_kaf · 2025-03-15 09:43:08 · 题解

最优策略下，第一个开始做的任务一定是准时开始的。若我们决定第一个做任务 i，那么总用时即为 s_i-1+\sum_{j=i}^{n}t_j，答案即为 \max(s_i-1+\sum_{j=i}^{n}t_j)。

用一颗线段树维护每一位开始的总和。插入新任务 (s,t) 时，给 [1,s] 加上 t。若目前它是第一个在时间 s 开始的任务，则额外给 [s,s] 加上 s-1。删除操作取反即可。

const ll N=1e6+10,mod=1e6+3;
ll Q,last,sgtr[N*4],lz[N*4],cnt[N];
vector<ll> ss,tt;

ll ls(ll p){
    return p*2;
}

ll rs(ll p){
    return p*2+1;
}

void pushdown(ll p){
    sgtr[ls(p)]+=lz[p];
    sgtr[rs(p)]+=lz[p];
    lz[ls(p)]+=lz[p];
    lz[rs(p)]+=lz[p];
    lz[p]=0;
}

void pushup(ll p){
    sgtr[p]=max(sgtr[ls(p)],sgtr[rs(p)]);
}

void upd(ll p,ll l,ll r,ll ql,ll qr,ll v){
    if(r<ql or l>qr) return;

    if(ql<=l and r<=qr){
        sgtr[p]+=v;
        lz[p]+=v;
    }else{
        if(lz[p]) pushdown(p);

        ll mid=(l+r)/2;
        upd(ls(p),l,mid,ql,qr,v);
        upd(rs(p),mid+1,r,ql,qr,v);
        pushup(p);
    }
}

int main(){
    ss.pb(-1);
    tt.pb(-1);
    cin>>Q;

    count(Q){
        char ty;
        cin>>ty;

        if(ty=='A'){
            ll s,t;
            cin>>s>>t;
            s=(s+last)%mod;
            t=(t+last)%mod;
//          cout<<"s="<<s<<",t="<<t<<'\n';
//          pause;
            ss.pb(s);
            tt.pb(t);
            upd(1,1,N,1,s,t);

            if(cnt[s]==0) upd(1,1,N,s,s,s-1);

            cnt[s]++;
        }else{
            ll x;
            cin>>x;
            x=(x+last)%mod;
//          cout<<"x="<<x<<'\n';
            upd(1,1,N,1,ss[x],-tt[x]);
            cnt[ss[x]]--;

            if(cnt[ss[x]]==0) upd(1,1,N,ss[x],ss[x],1-ss[x]);
        }

        last=sgtr[1];
        cout<<last<<'\n';
    }
}