[ARC085F] NRE

## 题目描述 个全为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

[problemUrl]: https://atcoder.jp/contests/arc085/tasks/arc085_d 全ての要素が $ 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 $

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

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 何も操作を行わないのが最適な時もあります。