#534. 「LibreOJ Round #6」花团

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: liu_cheng_ao

题目描述

「Alice —— !」「Karen —— !」

Alice 和 Karen 家边的大花坛给了她们无尽的欢乐。

这天 Karen 想重新规划一下花坛在一年里的外观。但是由于花朵各有其花期,而且花市上的选择实在太多了,所以她把问题进行了一些抽象,希望擅长程序设计的你可以为她解决。

物品集合 SS 初始为空,按时间递增顺序依次给出 qq 次操作,操作如下:

  • 1 v w e\texttt{1 v w e} 表示在 SS 中加入一个体积为 vv 价值为 ww 的物品,第 ee 次操作结束之后移除该物品。
  • 2 v\texttt{2 v} 表示询问。你需要回答:
    1. 当前 SS 是否存在一个子集使得子集中物品体积和为 vv
    2. 当前 SS 的所有物品体积和为 vv 的子集中,价值和最大是多少(空集的价值和为 0)。

输入格式

第一行三个正整数 q,maxv,Tq,\text{maxv},T 表示操作数、最大可能的 vv、及是否强制在线。

接下来 qq 行每行描述一个操作。
设修正值 d=T×lastansd=T\times \text{lastans}。这里 lastans\text{lastans} 表示上次询问的两个答案的异或和,若没有上次询问则 lastans=0\text{lastans}=0
则第 ii 行中,第一个整数 op\text{op} 表示操作类型;
若操作类型为 11,则接下来三个整数 v,w,ev',w',e' 表示加入一个体积为 vi=vdv_i=v'-d,价值为 wi=wdw_i=w'-d,在第 ei=ede_i=e'-d 时间后被移除的物品;
若操作类型为 22,则接下来一个整数 vv' 表示询问 vi=vdv_i=v'-d
一行中相邻整数以单个空格分隔。

输出格式

对于每个询问(22 类型的操作)输出一行两个整数 eemaxw\text{maxw},由空格分隔。

若不存在这样的子集,e=maxw=0e=\text{maxw}=0
否则 e=1e=1maxw\text{maxw} 为最大的价值和。

样例

样例输入 1

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

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

数据范围与提示

对于所有数据,1q15000,1vimaxv15000,0wi15000,ieiq1\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%40\% 的分数;若问题 2 回答全对,则另得 60%60\% 的分数。每个子任务的得分是其中各测试点的最小值。
注意,即使你只回答了一个问题,每次仍要输出两个整数,以免答案错位。

Subtask # 分值 q,vq,v 的限制 TT 的限制
1 1515 q18,v15000q\le 18,v\le 15000 T=0T=0
2 2020 q,v1000q,v\le 1000 T{0,1}T\in\{0,1\}
3 2020 q,v6000q,v\le 6000 T=0T=0
4 2020 q,v10000q,v\le 10000 T=0T=0
5 2525 q,v15000q,v\le 15000 T{0,1}T\in\{0,1\}