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