题目类型说明

这是一道提交函数题。

你需要实现如下函数：

void init(std::vector<int> A);
std::vector<int> queries(std::vector<std::pair<int, int>> S);
void update(int I, int V);

其中：

• A：长度为 N 的初始数组，元素值均在 1..N 之间；
• S：若干个区间查询，每个查询由一对下标 (l_i, r_i) 构成，满足 0 <= l_i <= r_i <= N-1；
• I：要修改的位置；
• V：新的值，且总满足 1 <= V <= N。

init 在每组测试开始时会被调用一次。之后会交替调用 queries 和 update。

对于每次 queries(S)，你需要按输入顺序返回一个数组，第 i 个元素表示区间 [l_i, r_i] 中恰好出现一次的数值个数。

题目描述

Deni 有一个很大，甚至可以说非常大的数组，长度为 N，其中每个元素的值都在 1 到 N 之间。

她会不断研究这个数组的若干个子数组，并统计其中唯一值的数量。这里称一个值在某个子数组中是“唯一”的，当且仅当它在该子数组中恰好出现一次。

有时 Deni 还会修改数组中的某些元素。她很快就厌倦了自己手动做这些事情，于是请你编写程序 unique 来替她完成。

约束条件

• 1 <= N <= 10^5
• 1 <= Q <= 10^5
• 0 <= U <= 10^4
• 其中 Q = E + U
  • E 表示总查询次数；
  • U 表示总修改次数。

子任务

通过 (∗) 表示以下额外限制：对于每个被查询的子数组，其中任意一个值最多出现两次。

只有当某个子任务及其依赖子任务的所有测试点全部通过时，才可获得该子任务分数。

样例

输入

10 10
0
4 3 3 2 2 1 3 4 3 4
1 4 9
2 7 1
2 8 6
1 7 9
1 5 9
1 0 1
1 8 9
2 5 2
1 1 5
1 2 7

输出

2
3
3
2
2
0
1

样例解释

输入格式与下文“本地 grader”部分一致。

被查询的数组状态依次为：

• 4 3 3 2 2 1 3 4 3 4
• 4 3 3 2 2 1 3 1 6 4
• 4 3 3 2 2 1 3 1 6 4
• 4 3 3 2 2 1 3 1 6 4
• 4 3 3 2 2 1 3 1 6 4
• 4 3 3 2 2 2 3 1 6 4
• 4 3 3 2 2 2 3 1 6 4

样例测试属于评测系统中的子任务 0，不影响正式得分。

本地 grader

输入格式

• 第 1 行：两个整数 N 和 Q，表示数组长度以及总操作数；
• 第 2 行：一个布尔值 f：
  • 当 f = 1 时，保证不会有修改，且所有查询会通过一次 queries 调用给出；
  • 当 f = 0 时，每次查询都会单独作为一次 queries 调用给出；
• 第 3 行：N 个整数，表示初始数组；
• 第 4 行到第 4 + Q - 1 行：每行三个整数 t, x, y：
  • 当 t = 1 时，表示查询区间 [x, y]；
  • 当 t = 2 时，表示把 A[x] 修改为 y。

输出格式

• 第 i 行输出第 i 次 queries 调用返回的所有值。