AT_jsc2019_final_h.Distinct Integers

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个长度为 $N$ 的数列 $A_0,A_1,\cdots,A_{N-1}$ 。请你回答 $Q$ 个查询。具体来说，对于第 $i$ 个查询（ $0 \leq i \leq Q-1$ ），给定整数 $T_i,X_i,Y_i$ ，请按如下方式操作：

当 $T_i=0$ 时：将 $A_{X_i}$ 替换为 $Y_i$ 。
当 $T_i=1$ $T_{i} = 1$ 时：请回答满足以下条件的整数对 $(l,r)$ $(l, r)$ 的个数（ $X_i \leq l < r \leq Y_i$ $X_{i} \leq l < r \leq Y_{i}$ ）：
- $A_l,A_{l+1},\cdots,A_{r-1}$ 都互不相同。

输入格式

输入以如下格式从标准输入给出。

$N$ $Q$ $A_0$ $A_1$ $\cdots$ $A_{N-1}$ $T_0$ $X_0$ $Y_0$ $T_1$ $X_1$ $Y_1$ $\vdots$ $T_{Q-1}$ $X_{Q-1}$ $Y_{Q-1}$

输出格式

对于每个 $T_i=1$ 的查询，按照查询给出的顺序，每行输出一个答案。

输入输出样例

输入#1

输出#1

8
15
5

输入#2

30 30
14 24 18 7 20 10 0 27 27 29 27 20 23 29 27 0 11 10 0 12 19 7 21 12 11 7 27 11 21 0
1 6 21
1 27 29
0 23 21
1 1 5
0 3 24
1 3 6
1 9 16
1 16 26
1 0 11
0 29 27
0 25 29
0 4 24
1 10 23
1 18 24
0 22 14
0 13 10
1 2 29
0 7 12
0 27 14
1 18 20
0 23 7
0 15 20
1 1 24
0 24 7
0 24 20
1 7 16
0 15 27
0 23 10
1 11 13
1 4 8

输出#2

说明/提示

限制条件

$1 \leq N \leq 5 \times 10^5$
$1 \leq Q \leq 5 \times 10^5$
$0 \leq A_i \leq N-1$
$0 \leq T_i \leq 1$
$0 \leq X_i \leq N-1,\ 0 \leq Y_i \leq N-1$ （ $T_i=0$ ）
$0 \leq X_i < Y_i \leq N$ （ $T_i=1$ ）
至少存在一个 $T_i=1$ 的查询。
输入的所有值均为整数。

样例解释 1

以第 4 个查询为例。当该查询给出时， $A=(0,1,4,3,4)$ 。满足条件的 $(l,r)$ 共有 $5$ 组，分别为 $(l,r)=(2,3),(2,4),(3,4),(3,5),(4,5)$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页