M - Equal Queries Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ 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 < j \le N かつ A_i = A_j であるような整数の組 (i,j) の数を答える。

制約

  • 入力は全て整数
  • 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

入力

入力は以下の形式で標準入力から与えられる。但し、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 回目のクエリに対する解答を出力せよ。

入力例 1

8
3 1 4 1 5 9 2 6
6
1 3 5
2 4 1
7 7 9
5 8 2
1 8 1000000000
2 7 999999999

出力例 1

6
4
5
9
28
16
  • はじめ、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 です。

Score : 6 points

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of length N: A = (A_1, A_2, \dots, A_N).

You will be given Q queries, which should be processed in the order they are given. In each query, given integers l, r, and x, do as follows:

  • change each of the elements A_l, A_{l+1}, \dots, A_r to x;
  • then, report the number of pairs of integers (i, j) such that 1 \le i < j \le N and A_i = A_j.

Constraints

  • All values in input are integers.
  • 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)
  • For every query, the following holds:
    • 1 \le l \le r \le N
    • 1 \le x \le 10^9

Input

Input is given from Standard Input in the following format, where Query_i represents the i-th query:

N
A_1 A_2 \cdots A_N
Q
Query_1
Query_2
\vdots
Query_Q

Each query is in the following format:

l r x

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

8
3 1 4 1 5 9 2 6
6
1 3 5
2 4 1
7 7 9
5 8 2
1 8 1000000000
2 7 999999999

Sample Output 1

6
4
5
9
28
16
  • Initially, we have A=(3,1,4,1,5,9,2,6).
  • The 1-st query makes A (5,5,5,1,5,9,2,6). The response to this query should be 6.
  • The 2-nd query makes A (5,1,1,1,5,9,2,6). The response to this query should be 4.
  • The 3-rd query makes A (5,1,1,1,5,9,9,6). The response to this query should be 5.
  • The 4-th query makes A (5,1,1,1,2,2,2,2). The response to this query should be 9.
  • The 5-th query makes A (1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000). The response to this query should be 28.
  • The 6-th query makes A (1000000000,999999999,999999999,999999999,999999999,999999999,999999999,1000000000). The response to this query should be 16.