[CTSC2015] 日程管理

题意

幽香是幻想乡中一个非常有地位的人。她日理万机，事务繁多，反倒自己已经快管理不过来了。于是他决定开发一个日程管理软件来帮助自己管理任务。

对于每个任务\(i\)有一个对应的截止日期\(t_i\)以及收益\(p_i\)，表示若幽香能在不晚于第\(t_i\)天完成这个任务，便可以得到\(p_i\)的收益。幽香办事的能力非常强，任何任务都可以用恰好一天的时间做完。但由于任务实在太多了，有时候并不能完成所有任务，于是幽香会想知道这个情况下，完成任务可以给她带来的最大的累积收益是多少。

由于幻想乡的人们十分善变，任务总是不断发生着变化。幽香希望这个管理软件还能够支持插入一个任务，和删除一个任务的操作。

具体的说，幽香希望支持以下2个操作：

1.ADD t p：表示新添一个截止日期为t，收益为p的任务。

2.DEL t p：表示删除一个截止日期为t，收益为p的任务。如果有多个这样的任务，只删除一个。数据保证这样的任务一定存在。

在每次操作执行完毕后，你都需要输出能够完成的任务的最大收益和。

幽香一共有T天需要安排，从第1天到第T天。你能帮助他写出这个高效率的软件吗？

题解

考虑将模型转化。
我们将任务的使用情况映射到天数上面。
对第 \(i\) 天，我们记 \(s_i\) 表示第 \(i\) 天能够执行的任务数量，初始时 \(s_i=i\)。

加入。

我们如果在 \(pos\) 这个位置上放了一个任务，则 \([pos,T]\) 的 \(s_i\) 进行区间减 \(1\)。
如果 \(\min_{i=pos}^{i\leq T}s_i > 0\) ，则说明没有影响，可以直接放，反之不能。
不能的话我们显然要调整，我们删除某一任务，然后加入这个任务。
考虑加入之前就已经是最优的状态了，所以我们找到 \([pos,T]\) 中第一个值为 \(0\) 的位置 \(k\)。
我们在 \([1,k-1]\) 中选择贡献最小的任务，如果贡献没有新放的大，就撤销做一个区间加，然后再把当前任务加入。

删除

其实和加入类似。
删除一个任务就对应着一个后缀区间加。
同理，我们找到第一个为 \(0\) 的位置 \(k\)，然后在 \([k+1,T]\) 中找一个未选的可加入的贡献最大的任务加入即可。

最后由于每天可以有多个任务，并且还有撤销操作，用 multiset维护未选集合与总集合即可，代码中还有些小细节。
code

...

这个贪心其实挺显然的，不一定是按什么排个序之后做。
我们可以考虑从一个最优状态推向另一个最优状态，可以有一个‘反悔’的操作。