#P4068. [Ctsc2015]app

    ID: 1747 传统题 10000ms 233MiB 尝试: 100 已通过: 24 难度: 9 上传者: 标签>CF2800省选/NOI-拟阵交换性质反悔贪心懒标记线段树线段树上二分普通线段树有序多重集合

[Ctsc2015]app

题目描述

幽香是幻想乡中一个非常有地位的人。

她日理万机,事务繁多,反倒自己已经快管理不过来了。

于是他决定开发一个日程管理软件来帮助自己管理任务。

对于每个任务 ii 有一个对应的截止日期 tit_i 以及收益 pip_i,表示若幽香能在不晚于第 tit_i 天完成这个任务,便可以得到 pip_i 的收益。

幽香办事的能力非常强,任何任务都可以用恰好一天的时间做完。

但由于任务实在太多了,有时候并不能完成所有任务,于是幽香会想知道这个情况下,完成任务可以给她带来的最大的累积收益是多少。

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

具体的说,幽香希望支持以下 22 个操作:

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

2.DEL t p 表示删除一个截止日期为 tt,收益为 pp 的任务。

如果有多个这样的任务,只删除一个。

数据保证这样的任务一定存在。

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

幽香一共有 TT 天需要安排,从第 11 天到第 TT 天。

你能帮助他写出这个高效率的软件吗?

输入格式

第一行有两个整数 TT 和 QQ,表示天数和操作的个数。

接下来 QQ 行,其中第 ii 行表示第 ii 个操作,形式为 ADD t p 或 DEL t p,其具体意义如题面所述。

输出格式

对每一次操作,输出一个整数在执行完该操作后幽香能够获得的最大收益和。

5 10
ADD 1 5811
ADD 3 5032
DEL 3 5032
ADD 3 5550
ADD 5 3486
DEL 1 5811
DEL 3 5550
ADD 4 5116
ADD 3 9563
ADD 5 94
5811
10843
5811
11361
14847
9036
3486
8602
18165
18259

数据规模与约定

对于本站的全部评测数据,1≤T,Q≤3×1051\le T,Q\le3\times10^5,1≤t≤T1\le t\le T,1≤p≤1041\le p\le10^4。每天至多完成一个任务,允许不做任务。

题目来源