#F. Yet Another 伟大的数据结构问题

    传统题 文件IO:ds 2000ms 256MiB

Yet Another 伟大的数据结构问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

本道题目为本场比赛的 Bonus 题目,整体思维、难度、技巧以及知识面上与 S 组略有不同,欢迎各位强者来挑战~

赛时公告(12:29):本题的大样例和数据更新。

Description

nn 个集合 S1,S2,,SnS_1,S_2,\cdots,S_n,初始全为空,需要 支持三种操作:

  • 1 l r x1 \space l \space r \space x:将 xx 插入 Sl,,SrS_l,\cdots,S_r
  • 2 l r x2 \space l \space r \space x:将 xxSl,,SrS_l,\cdots,S_r 删除。
  • 3 u v3 \space u \space v:询问 SuS_u 是否为 SvS_v 的子集。

请留意数据范围。

Format

Input

第一行两个正整数 n,mn,m,表示集合个数和操作个数。

接下来 mm 行,每行为以下三种形式之一:

  • 1 l r x1 \space l \space r \space x
  • 2 l r x2 \space l \space r \space x
  • 3 u v3 \space u \space v

分别表示一种操作。

Output

对于每个 33 操作,输出一行 YESNO 以回答询问。

Samples

5 10
1 1 5 1
1 2 4 2
3 1 2
3 2 2
3 2 3
1 3 3 3
3 1 3
2 2 4 2
1 5 5 5
3 5 3
YES
YES
YES
YES
NO
最后一次修改操作 S1S_1 S2S_2 S3S_3 S4S_4 S5S_5
1 1 5 11 \space 1 \space 5 \space 1 {1}\{1\} {1}\{1\} {1}\{1\}
1 2 4 21 \space 2 \space 4 \space 2 {1,2}\{1,2\} {1,2}\{1,2\} {1,2}\{1,2\}
1 3 3 31 \space 3 \space 3 \space 3 {1,2,3}\{1,2,3\}
2 2 4 22 \space 2 \space 4 \space 2 {1}\{1\} {1,3}\{1,3\} {1}\{1\}
1 1 5 11 \space 1 \space 5 \space 1 {1,5}\{1,5\}

以下的全部样例请参考下发文件:

戳这里下载下发文件

见下发文件中的 ex_ds2.in
见下发文件中的 ex_ds2.ans

此样例符合子任务 22 的限制。

见下发文件中的 ex_ds3.in
见下发文件中的 ex_ds3.ans

此样例符合子任务 33 的限制。

见下发文件中的 ex_ds4.in
见下发文件中的 ex_ds4.ans

此样例符合子任务 44 的限制。

见下发文件中的 ex_ds5.in
见下发文件中的 ex_ds5.ans

此样例符合子任务 55 的限制。

见下发文件中的 ex_ds6.in
见下发文件中的 ex_ds6.ans

此样例符合子任务 66 的限制。

见下发文件中的 ex_ds7.in
见下发文件中的 ex_ds7.ans

此样例符合子任务 77 的限制。

Limitation

对于所有数据,有:

  • 1n,m1051 \le n,m \le 10^5
  • 1x1051 \le x \le 10^5
  • 1lr1051 \le l \le r \le 10^5
  • 1u,v1051 \le u,v \le 10^5
  • 对于 11 操作,保证操作之前这些集合中均不包含 xx
  • 对于 22 操作,保证在这次操作之前有一个对应的 1 l r x1 \space l \space r \space x 操作且这个操作插入的 xx 没被删除。
  • 对于 33 操作,令 LIM=SvSuLIM=|S_v|-|S_u|,保证 0LIM20 \le LIM \le 2,其中 Su,Sv|S_u|,|S_v| 分别表示集合 u,vu,v 的大小。
子任务 特殊性质 分值
11 答案均为 NO 11
22 n,m2000n,m \le 2000 55
33 x10x \le 10 1212
44 所有11 操作的 xx 互不相同,没有 22 操作 2121
55 LIM=0LIM=0 1212
66 LIM1LIM \le 1 2323
77 2626

Fun Fact: subtask 11 本来设置的是 0.450.45 分,但因为 OJ 显示不了小数,就改成 11 了。

[YDRG#003 Div. 1] YDSP-S 组赛前模拟 · 云斗杯十月 Golden Round

已参加
状态
已结束 (已参加)
规则
OI
题目
6
开始于
2023-10-14 8:30
结束于
2023-10-14 13:30
持续时间
5 小时
主持人
参赛人数
287