← 返回题目列表

AtCoder · arc085_d

F. 无需重新计算

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

分数: 1000 点

问题陈述

给你一个序列 a = \{a_1, ..., a_N\} 全为零,以及一个序列 b = \{b_1, ..., b_N\} 组成 0 和 1。两者的长度都是 N.

您可以执行 Q 种操作。 i第次操作如下:

  • 替换每个 a_{l_i}, a_{l_i + 1}, ..., a_{r_i} 与 1.

最小化之间的汉明距离 a 和 b,即数量 i 这样 a_i \neq b_i,通过执行一些 Q 操作。

约束

  • 1 \leq N \leq 200,000
  • b 包括 0 和 1.
  • 1 \leq Q \leq 200,000
  • 1 \leq l_i \leq r_i \leq N
  • If i \neq j,或者 l_i \neq l_j or r_i \neq r_j.

输入

输入由标准输入按以下格式给出:

N
b_1 b_2 ... b_N
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q

输出

打印可能的最小汉明距离。


样本输入 1

3
1 0 1
1
1 3

示例输出 1

1

如果您选择执行该操作, a 将成为 \{1, 1, 1\},汉明距离为 1.


示例输入 2

3
1 0 1
2
1 1
3 3

示例输出 2

0

如果执行这两个操作, a 将成为 \{1, 0, 1\},汉明距离为 0.


示例输入 3

3
1 0 1
2
1 1
2 3

示例输出 3

1

示例输入 4

5
0 1 0 1 0
1
1 5

示例输出 4

2

最好不执行任何操作。


示例输入 5

9
0 1 0 1 1 1 0 1 0
3
1 4
5 8
6 7

示例输出 5

3

示例输入 6

15
1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
9
4 10
13 14
1 7
4 14
9 11
2 6
7 8
3 12
7 13

示例输出 6

5

示例输入 7

10
0 0 0 1 0 0 1 1 1 0
7
1 4
2 5
1 3
6 7
9 9
1 5
7 9

示例输出 7

1