专栏文章

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

SSunburstFan
P11861题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipcqrnj
此快照首次捕获于
2025/12/03 09:52
3 个月前
此快照最后确认于
2025/12/03 09:52
3 个月前
查看原文

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

题目大意

维护一个待办任务列表，支持两种加密更新操作：
  • A s t：添加一个任务（发布时间 ss，所需时间 tt）
  • D x：删除第 xx 个加入的任务
    每次更新后，求最早完成所有任务的时刻（任务必须按顺序连续完成）。

解题思路

利用线段树维护时间区间的累积值，支持区间加法更新。
对于每次任务添加或删除，通过更新相应区间来调整整体完成时间（即树根的最大值）。
每次操作均为 O(log⁡N)O(\log N)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...