分数: 366 分
问题陈述
高桥负责一栋大型建筑的照明管理系统。该建筑有 N 房间,每个房间都分配了一个编号 1 to N.
每个房间的照明有两种状态:“关”和“开”。最初,所有房间的灯都关闭。
高桥表演 Q 操作。在 i第次操作 (1 \leq i \leq Q),他切换房间号在之间的所有房间的照明状态 L_i 和 R_i,包括在内。也就是说,如果灯关闭,则将其打开;如果灯打开,则将其关闭。
该建筑物有 M “会议室”,其房间号为 B_1, B_2, \ldots, B_M (不一定按升序排列)。
毕竟 Q 操作已完成,查找其中的房间数 M 指定会议室灯亮。
约束
- 1 \leq N \leq 10^9
- 1 \leq M \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq B_i \leq N (1 \leq i \leq M)
- 全部 B_i 是不同的
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
- 所有输入值均为整数
输入
N M Q B_1 B_2 \ldots B_M L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含三个空格分隔的整数: N 代表房间总数, M 代表会议室数量,以及 Q 代表操作次数。
- 第二行包含 M 空格分隔的整数 B_1, B_2, \ldots, B_M 代表会议室的房间号。
- 以下 Q 行提供每个操作的信息。
- 的 (2 + i)第行 (1 \leq i \leq Q) 包含两个空格分隔的整数:开始 L_i 并结束 要切换的间隔的 R_i 要切换的间隔 i第次操作。
输出
在一行上打印所有操作完成后灯亮的会议室数量。
示例输入 1
10 3 2 2 5 8 1 6 4 9
示例输出 1
2
示例输入 2
20 5 4 3 7 12 15 18 1 10 5 15 8 12 3 7
示例输出 2
2
示例输入 3
1000000000 10 8 1 100 999999999 500000000 250000000 750000000 123456789 987654321 42 1000000000 1 500000000 250000000 750000000 100 123456789 42 42 500000000 1000000000 1 100 987654321 999999999 42 100
示例输出 3
2