题目描述

全ての要素が $0$ の数列 $a\ =\ \{a_1,\ ...,\ a_N\}$ と，$0$ と $1$ からなる数列 $b\ =\ \{b_1,\ ...,\ b_N\}$ が与えられます。 どちらも長さは $N$ です。

あなたは $Q$ 種類の操作を行うことが可能です。$i$ 種類目の操作は以下のような動作です。

• $a_{l_i},\ a_{l_i\ +\ 1},\ ...,\ a_{r_i}$ を全て $1$ に書き換える

$Q$ 種類の操作のうちいくつかを行い，$a$ と $b$ のハミング距離， つまり $a_i\ \neq\ b_i$ なる $i$ の数を最小化してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

ハミング距離の最小値を出力してください。

题目大意

题目描述

个全为0的数组a，给一个数组b和q个操作，每个操作将数组a指定区间改成1，问合理选择部分操作后使得两个数组的∑ ai≠bi 最小。

输入格式

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

输出格式

即为最小的∑ ai≠bi

3
1 0 1
1
1 3

1

3
1 0 1
2
1 1
3 3

0

3
1 0 1
2
1 1
2 3

1

5
0 1 0 1 0
1
1 5

2

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

3

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

5

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

1

提示

制約

• $1\ \leq\ N\ \leq\ 200,000$
• $b$ は $0,\ 1$ からなる
• $1\ \leq\ Q\ \leq\ 200,000$
• $1\ \leq\ l_i\ \leq\ r_i\ \leq\ N$
• $i\ \neq\ j$ ならば $l_i\ \neq\ l_j$ または $r_i\ \neq\ r_j$

Sample Explanation 1

操作を行うと $a\ =\ \{1,\ 1,\ 1\}$ になり，ハミング距離は $1$ となります。

Sample Explanation 2

両方の操作を行うと $a\ =\ \{1,\ 0,\ 1\}$ になり，ハミング距離は $0$ となります。

Sample Explanation 4

何も操作を行わないのが最適な時もあります。