分数: 625 点
问题陈述
有 N 套 S_1, \ldots,S_N。最初,所有集合都是空的。
你被给予 Q 按以下格式查询。按顺序处理它们。
- 类型 1:给出为
1 L R x。对于每个 S_i 满意 L \leq i \leq R,添加 x. - 类型 2:给出为
2 L R x。对于每个 S_i 满意 L \leq i \leq R,删除 x. - 类型 3:给出为
3 L R。找出其中的最大元素数 S_i 满意 L \leq i \leq R,以及达到此最大值的组数。
约束
- 1\leq N \leq 3\times 10^5
- 1\leq Q \leq 3\times 10^5
- 对于每个查询, 1 \leq L \leq R \leq N.
- 对于类型 1,2 查询, 1 \leq x \leq 60.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
在这里, \mathrm{query}_i 代表 i-th 查询,每个查询均以以下格式之一给出,如问题陈述中所示:
1 L R x
2 L R x
3 L R
输出
让 q 是类型的数量 3 查询,并打印 q 行。
的
树的 i- 第行应包含 x,y 用空格分隔,其中 x 是元素的最大数量, y 是达到此最大值的组数 i第类型 3 查询。
示例输入 1
4 7 1 1 2 10 1 2 4 20 3 1 3 2 1 2 20 1 2 3 10 3 1 2 3 1 4
示例输出 1
2 1 1 2 2 1
- 最初 (S_1,S_2,S_3,S_4)=(\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace).
- 的 树的 1-st 查询添加 10 to S_1,S_2,导致 (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace\rbrace,\lbrace\rbrace).
- 的 树的 2-nd 查询添加 20 to S_2,S_3,S_4,导致 (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace).
- 对于 3-rd查询,其中元素的最大个数 S_1,S_2,S_3 is 2 实现者 S_2,所以打印
2 1. - 的 树的 4-th 查询删除 20 来自 S_1,S_2,导致 (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace).
- 的 树的 5-第一个查询添加 10 to S_2,S_3,导致 (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace).
- 对于 6第一次查询,其中元素的最大数量 S_1,S_2 is 1 实现者 S_1,S_2,所以打印
1 2. - 对于 7第一次查询,其中元素的最大数量 S_1,S_2,S_3,S_4 is 2 实现者 S_3,所以打印
2 1.