自动搬运

查看原文

来自洛谷，原作者为

	chenly8128 God helps those who help themselves.

搬运于2025-08-24 23:10:54，当前版本为作者最后更新于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;
}