分数: 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.