3986: 「LibreOJ Round #6」花团
内存限制：256 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
> 「Alice —— !」「Karen —— !」
>
> Alice 和 Karen 家边的大花坛给了她们无尽的欢乐。
>
> 这天 Karen 想重新规划一下花坛在一年里的外观。但是由于花朵各有其花期，而且花市上的选择实在太多了，所以她把问题进行了一些抽象，希望擅长程序设计的你可以为她解决。
物品集合 $S$ 初始为空，按时间递增顺序依次给出 $q$ 次操作，操作如下：
* $\texttt{1 v w e}$ 表示在 $S$ 中加入一个体积为 $v$ 价值为 $w$ 的物品，第 $e$ 次操作结束之后移除该物品。
* $\texttt{2 v}$ 表示询问。你需要回答：
1. 当前 $S$ 是否存在一个子集使得子集中物品体积和为 $v$。
2. 当前 $S$ 的所有物品体积和为 $v$ 的子集中，价值和最大是多少（空集的价值和为 0）。
输入
第一行三个正整数 $q,\text{maxv},T$ 表示操作数、最大可能的 $v$、及是否强制在线。
接下来 $q$ 行每行描述一个操作。
设修正值 $d=T\times \text{lastans}$。这里 $\text{lastans}$ 表示上次询问的**两个答案的异或和**，若没有上次询问则 $\text{lastans}=0$。
则第 $i$ 行中，第一个整数 $\text{op}$ 表示操作类型；
若操作类型为 $1$，则接下来三个整数 $v',w',e'$ 表示加入一个体积为 $v_i=v'-d$，价值为 $w_i=w'-d$，在第 $e_i=e'-d$ 时间后被移除的物品；
若操作类型为 $2$，则接下来一个整数 $v'$ 表示询问 $v_i=v'-d$。
一行中相邻整数以单个空格分隔。
输出
对于每个询问（$2$ 类型的操作）输出一行两个整数 $e$ 和 $\text{maxw}$，由空格分隔。
若不存在这样的子集，$e=\text{maxw}=0$；
否则 $e=1$，$\text{maxw}$ 为最大的价值和。
样例输入 复制
12 10 0
1 1 1 12
1 6 0 12
1 10 7 8
1 3 8 7
2 6
2 9
2 10
2 10
2 10
1 3 2 11
2 4
2 4样例输出 复制
1 0
1 8
1 9
1 7
0 0
1 3
0 0提示
输入样例2
19 20 1 1 2 19 11 2 2 1 27 27 22 1 20 34 36 2 29 1 9 8 9 1 5 19 8 1 1 15 19 2 3 1 36 40 54 1 37 50 52 2 40 2 62 1 1 17 16 1 1 7 16 1 13 16 18 1 9 11 19 2 10 2 34
输出样例2
1 19 0 0 1 34 1 46 0 0 1 26 0 0
数据范围：对于所有数据，$1\le q\le 15000,1\le v_i\le \text{maxv}\le 15000,0\le w_i\le 15000,i\le e_i\le q$。 对于每个测试点，若问题 1 回答全对，则得 $40\%$ 的分数；若问题 2 回答全对，则另得 $60\%$ 的分数。每个子任务的得分是其中各测试点的最小值。 注意，即使你只回答了一个问题，每次仍要输出两个整数，以免答案错位。 |Subtask #|分值|$q,v$ 的限制|$T$ 的限制| |:-:|:-:|:-:|:-:| |1|$15$|$q\le 18,v\le 15000$|$T=0$| |2|$20$|$q,v\le 1000$|$T\in\{0,1\}$| |3|$20$|$q,v\le 6000$|$T=0$| |4|$20$|$q,v\le 10000$|$T=0$| |5|$25$|$q,v\le 15000$|$T\in\{0,1\}$|