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

SunburstFan · 2025-05-10 14:54:24 · 题解

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

题目大意

维护一个待办任务列表，支持两种加密更新操作：

• A s t：添加一个任务（发布时间 s，所需时间 t）
• D x：删除第 x 个加入的任务
  每次更新后，求最早完成所有任务的时刻（任务必须按顺序连续完成）。

解题思路

利用线段树维护时间区间的累积值，支持区间加法更新。

对于每次任务添加或删除，通过更新相应区间来调整整体完成时间（即树根的最大值）。

每次操作均为 O(\log N)。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
const int mod=1e6+3;

int m,seg[(N<<2)+100],lz[(N<<2)+100];
string tmp;int s,t,x,last;
int l[N],r[N],cnt;

namespace seg_tree{
    void pushdown(int rt){
        seg[rt<<1]+=lz[rt];
        seg[rt<<1|1]+=lz[rt];
        lz[rt<<1]+=lz[rt];
        lz[rt<<1|1]+=lz[rt];
        lz[rt]=0;
    }
    void pushup(int rt){
        seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);
    }
    void add(int L,int R,int v,int l,int r,int rt){
        if(L<=l&&R>=r){
            lz[rt]+=v;
            seg[rt]+=v;
            return;
        }
        pushdown(rt);
        int mid=(l+r)>>1;

        if(mid>=L)add(L,R,v,l,mid,rt<<1);
        if(mid<R)add(L,R,v,mid+1,r,rt<<1|1);

        pushup(rt);
    }
}
using namespace seg_tree;

int ct[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>m;
    while(m--){
        cin>>tmp;

        if(tmp[0]=='A'){
            cin>>s>>t;
            l[++cnt]=s=(s+last)%mod;
            r[cnt]=t=(t+last)%mod;

            add(1,s,t,1,N,1);
            add(s,s,ct[s]++?0:s-1,1,N,1);
        }

        else if(tmp[0]=='D'){
            cin>>x;
            x=(x+last)%mod;

            add(1,l[x],-r[x],1,N,1);
            add(l[x],l[x],-(--ct[l[x]]?0:l[x]-1),1,N,1);
        }

        last=seg[1];
        cout<<last<<'\n';
    }
    return 0;
}