Binary Sequence

Time Limit : 1 sec, Memory Limit : 262142 KB

E:バイナリ列 - Binary Sequence -

物語

わしはバイナリ大好きBonald.Brvin.Bnuthじゃ! オフトゥンフォード大学でバイナリ列の性質を研究しておってのお、Bnuthおじさんと呼ばれて、親しまれておるぞい! ちなみに、わしの名前「Bonald.Brvin.Bnuth」をASCIIコードからバイナリ化すると「1000010 1101111 1101110 1100001 1101100 1100100 101110 1000010 1110010 1110110 1101001 1101110 101110 1000010 1101110 1110101 1110100 1101000」になるぞい! 楽しいのお!

今日は、弟子が何やら面白そうな実験をすると言うからのお、朝から楽しみなんじゃ! どれどれ、どんなことをするんじゃの?

なんと!バイナリ列を書き換え続けることで、何らかの性質を見出したいとな! ふむ!これは、重要な発見の匂いがぷんぷんするぞい! さあ、さあ、実験を始めようではないか! より詳細な設定を文章としてまとめておくぞい!

問題

長さnのバイナリ列x = (x_1, ..., x_n) (x_i \in \{0,1\}, i = 1,...,n) が与えられる。バイナリ列xに対して2つの関数f(x)g(x)を以下のように定義する。

f(x) = Σ_{i=1}^{n} x_i = x_1 + x_2 + ... + x_n
g(x) = Σ_{i=1}^{n-1} x_i x_{i+1} = x_1 x_2 + x_2 x_3 + ... x_{n-1} x_n

今、バイナリ列xに対して以下のような変更操作をq回行う。j回目の変更操作はl_j, r_j, b_j (1 \leq l_j \leq r_j \leq n, b_j \in \{0,1\}, j = 1,...,q) で与えられ、これはバイナリ列xl_j番目からr_j番目をb_jに置き換える操作に対応する。各変更操作の後でf(x) - g(x)を求めよ。

入力形式

n
x
q 
l_1 r_1 b_1
...
l_q r_q b_q

1行目にはバイナリ列の長さを表す整数nが与えられる。 2行目にはバイナリ列xを表せす文字列が与えられる。 3行目にはクエリの回数を表す整数qが与えられる。 続くq行のうちi行目には、i回目のクエリに関する情報l_i, r_i, b_iがこの順で空白区切りで与えられる。

制約

  • 2 \leq n \leq 100000
  • xは’0’、’1’からなる文字列
  • |x| = n
  • 1 \leq q \leq 100000
  • 1 \leq l_j \leq r_j \leq n, b_j \in \{0,1\}, j = 1,...,q

出力形式

i=1,...,qについて、i行目にi回目のクエリを処理した後のf(x) - g(x)の値を出力せよ。

入力例1

10
0101100110
3
3 3 1
1 6 0
2 5 1

出力例1

2
1
2

入力例2

8
00111100
3
8 8 1
4 5 0
7 8 1

出力例2

2
3
2

Source: Ritsumeikan University Programming Camp 2017 , Day 3, Shiga, Japan, 2017-03-24