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

chenly8128 · 2025-03-07 22:58:46 · 题解

赛时想出来怎么做已经晚了，时间不够写了。

知识点

• 线段树

思路

根据贪心思想，任意空闲时间点如果有任务，则立即开始任务，这么做一定不劣。

假定任务全部按照开始时间排好了顺序，总共有 n 个任务，设任务 x 是最后一个在发布时间准时准点开始的任务。由于一定有最早开始的任务，所以 x 一定存在。

可以发现，此时的最短用时即为 x 的开始时间，加上 x 和它之后开始的任务的总用时。

为了避免统计最后一个 x 在哪里（嫌麻烦），所以干脆把每一个任务都当作最后一个准时准点开始的任务，然后把计算出的结果取最大值，即为答案。答案为 \max(s_i - 1 + \sum_{j=i}^{n} + t_j)。

我们需要做的就是快速计算以上公式的值。

由于强制在线，且时间点个数不多，所以首选线段树。

• 对于每次增加任务，都将开始时间点和以前所有时间点的权值加上 t。如果开始的时间点目前没有别的开始任务，则在该时间点加上一个额外权值 s-1。
• 对于删除任务，采用逆的操作即可。
• 每次统计全局最大权值。

复杂度 O(q \log n)。

代码

#include <bits/stdc++.h>
#define int long long
#define ls(i) ((i)<<1)
#define rs(i) ((i)<<1|1)
using namespace std;
const int MAXN = 1e6+10;
const int mod = 1e6+3;
int m,seg[(MAXN<<2)+100],lz[(MAXN<<2)+100];
string tmp;int s,t,x,last;
int l[MAXN],r[MAXN],cnt;
void pushdown(int i) {
    seg[ls(i)] += lz[i];
    seg[rs(i)] += lz[i];
    lz[ls(i)] += lz[i];
    lz[rs(i)] += lz[i];
    lz[i] = 0;
}
void pushup(int i) {
    seg[i] = max(seg[ls(i)],seg[rs(i)]);
}
void add (int begin,int end,int v,int l,int r,int i) {
    if (begin <= l && end >= r) {
        lz[i] += v;
        seg[i] += v;
        return;
    }
    pushdown(i);
    int mid = (l+r) >> 1;
    if (mid >= begin) add(begin,end,v,l,mid,ls(i));
    if (mid < end) add(begin,end,v,mid+1,r,rs(i));
    pushup(i);
}
int ct[MAXN];
signed main (void) {
    ios::sync_with_stdio(false);
    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,MAXN,1);
            add(s,s,ct[s]++ ? 0 : s-1,1,MAXN,1);
        }
        else if (tmp[0] == 'D') {
            cin >> x;
            x = (x+last) % mod;
            add(1,l[x],-r[x],1,MAXN,1);
            add(l[x],l[x],-(--ct[l[x]] ? 0 : l[x]-1),1,MAXN,1);
        }
        last = seg[1];
        cout << last << '\n';
    }
    return 0;
}