← 返回题目列表

AtCoder · past202104_m

M. 相等查询

中文机器翻译题面 查看原题

分数: 6 点

警告

2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

我们有一个长度为 N: A = (A_1, A_2, \dots, A_N).

你将得到 Q 查询,应按照给出的顺序进行处理。在每个查询中,给定整数 l, r,和 x,执行如下操作:

  • 更改每个元素 A_l, A_{l+1}, \dots, A_r to x;
  • 然后,报告整数对的数量 (i, j) 这样 1 \le i < j \le N 和 A_i = A_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-st 查询使 A (5,5,5,1,5,9,2,6)。此查询的响应应该是 6.
  • 的 2-nd 查询使得 A (5,1,1,1,5,9,2,6)。此查询的响应应该是 4.
  • 的 3-rd 查询使 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.