AT_past202104_m 等しい数

[problemUrl]: https://atcoder.jp/contests/past202104-open/tasks/past202104_m 長さ $ N $ の数列 $ A\ =\ (A_1,\ A_2,\ \dots,\ A_N) $ があります。 クエリが $ Q $ 個与えられるので、与えられた順に処理してください。各クエリでは、整数 $ l,\ r,\ x $ が与えられます。クエリの内容は以下の通りです。 - $ A_l,\ A_{l+1},\ \dots,\ A_r $ を、全て $ x $ に変更する。 - その後、$ 1\ \le\ i\

入力は以下の形式で標準入力から与えられる。但し、$ Query_i $ は $ i $ 回目のクエリを表す。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ Q $ $ Query_1 $ $ Query_2 $ $ \vdots $ $ Query_Q $ 各クエリは以下の形式で与えられる。 > $ l $ $ r $ $ x $

$ Q $ 行出力せよ。 $ i $ 行目には、$ i $ 回目のクエリに対する解答を出力せよ。

### 注意 この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 入力は全て整数 - $ 2\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ Q\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ A_i\ \le\ 10^9 $ $ (1\ \le\ i\ \le\ N) $ - 全てのクエリは以下を満たす - $ 1\ \le\ l\ \le\ r\ \le\ N $ - $ 1\ \le\ x\ \le\ 10^9 $ ### Sample Explanation 1 \- はじめ、$ A=(3,1,4,1,5,9,2,6) $ です。 - $ 1 $ 回目のクエリを処理すると、$ A $ は $ (5,5,5,1,5,9,2,6) $ となります。 このクエリでの解答は $ 6 $ です。 - $ 2 $ 回目のクエリを処理すると、$ A $ は $ (5,1,1,1,5,9,2,6) $ となります。このクエリでの解答は $ 4 $ です。 - $ 3 $ 回目のクエリを処理すると、$ A $ は $ (5,1,1,1,5,9,9,6) $ となります。このクエリでの解答は $ 5 $ です。 - $ 4 $ 回目のクエリを処理すると、$ A $ は $ (5,1,1,1,2,2,2,2) $ となります。このクエリでの解答は $ 9 $ です。 - $ 5 $ 回目のクエリを処理すると、$ A $ は $ (1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000) $ となります。このクエリでの解答は $ 28 $ です。 - $ 6 $ 回目のクエリを処理すると、$ A $ は $ (1000000000,999999999,999999999,999999999,999999999,999999999,999999999,1000000000) $ となります。このクエリでの解答は $ 16 $ です。