← 返回题目列表

AtCoder · awc0086_c

C. 开关灯

中文机器翻译题面 查看原题

分数: 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