AT_abc430_g [ABC430G] Range Set Modifying Query

题目描述

有 $N$ 个集合 $S_1, \ldots, S_N$，初始时所有集合均为空。

你将得到 $Q$ 个操作，操作类型如下，请按顺序处理每个操作。

• 类型 $1$：给出 1 L R x。对于所有满足 $L \leq i \leq R$ 的 $S_i$，将 $x$ 加入集合。
• 类型 $2$：给出 2 L R x。对于所有满足 $L \leq i \leq R$ 的 $S_i$，将 $x$ 从集合中移除。
• 类型 $3$：给出 3 L R。查询所有满足 $L \leq i \leq R$ 的 $S_i$ 的元素个数的最大值，及达到该最大值的集合数量。

输入格式

输入以如下格式从标准输入读入：

$N\ Q\ \text{query}_1\ \vdots\ \text{query}_Q$

其中 $\text{query}_i$ 表示第 $i$ 个操作。每个操作满足如下格式之一：

$1\ L\ R\ x$

$2\ L\ R\ x$

$3\ L\ R$

输出格式

设类型 $3$ 的操作有 $q$ 次，请输出 $q$ 行。

第 $i$ 行应输出两个以空格分隔的整数 $x, y$，其中 $x$ 表示当前查询区间内集合元素数量的最大值，$y$ 表示达到该最大值的集合数量。

输入输出样例 #1

输入 #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

说明/提示

样例解释 1

• 初始时 $(S_1,S_2,S_3,S_4)=(\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace)$。
• 第 1 次操作，向 $S_1,S_2$ 加入 $10$，结果为 $(\lbrace 10\rbrace, \lbrace 10\rbrace, \lbrace\rbrace, \lbrace\rbrace)$。
• 第 2 次操作，向 $S_2,S_3,S_4$ 加入 $20$，结果为 $(\lbrace 10\rbrace, \lbrace 10,20\rbrace, \lbrace 20\rbrace, \lbrace 20\rbrace)$。
• 第 3 次操作，询问 $S_1,S_2,S_3$ 的最大元素个数为 $2$，仅 $S_2$ 达到，输出 2 1。
• 第 4 次操作，从 $S_1,S_2$ 移除 $20$，结果为 $(\lbrace 10\rbrace, \lbrace 10\rbrace, \lbrace 20\rbrace, \lbrace 20\rbrace)$。
• 第 5 次操作，向 $S_2,S_3$ 加入 $10$，结果为 $(\lbrace 10\rbrace, \lbrace 10\rbrace, \lbrace 10,20\rbrace, \lbrace 20\rbrace)$。
• 第 6 次操作，询问 $S_1,S_2$ 的最大元素个数为 $1$，$S_1,S_2$ 均达到，输出 1 2。
• 第 7 次操作，询问 $S_1,S_2,S_3,S_4$，最大为 $2$，$S_3$ 达到，输出 2 1。

数据范围

• $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$。
• 输入数据均为整数。

由 ChatGPT 5 翻译