每年圣诞节，Bajtazar 都会用一串彩色灯泡装饰他的房子。今年，Bajtazar 自己挑选了灯泡的颜色，但他很难做出决定，最终导致链条太长了。
Bajtazar 的妻子在某个热门网站上读到，今年的圣诞时尚要求链条包含尽可能多不同的“重复”。链条中的“重复”是指两个或更多连续的相同颜色的灯泡。如果重复部分的颜色不同或长度不同，则称这些重复是不同的。例如，灯泡序列 $1, 1, 1, 1, 2, 2, 2, 1, 1, 1$（其中数字 $1$ 和 $2$ 代表不同的颜色）包含五种不同的重复： $1, 1$ $1, 1, 1$ $1, 1, 1, 1$ $2, 2$ * $2, 2, 2$
Bajtazar 打算通过丢弃一定数量的起始和/或末尾灯泡来缩短他的链条。然而，他想知道在进行这样的操作后，链条中还会剩下多少种不同的重复。我们的主人公还不确定他到底打算移除多少个灯泡，因此他需要一个库来帮助他计算不同移除方式下的所需值。
交互
你的库必须提供以下函数：
inicjuj(n, t)该函数将在程序开始时被调用一次。你可以使用它来了解链条中灯泡的数量 $n$ 以及由向量 $t$ 给出的连续灯泡的颜色。灯泡颜色由 $0$ 到 $10^9$ 之间的整数表示。我们像向量 $t$ 的元素一样对它们进行编号，从 $0$ 到 $n - 1$。- C++:
void inicjuj(int n, vector<int> t);
- C++:
ile_powtorzen(a, b)调用此函数表示查询链条中从第 $a$ 个灯泡到第 $b$ 个灯泡（包含 $a$ 和 $b$）这一片段中不同重复的数量 ($0 \le a \le b < n$)。- C++:
int ile_powtorzen(int a, int b);
- C++:
你的程序不得读取任何数据（无论是从标准输入还是从文件）。它也不得向文件或标准输出写入任何内容。它可以写入标准诊断输出（stderr）——但请记住，这会消耗宝贵的时间。也不要声明 main 函数。
样例
| 操作 | 结果 | 说明 |
|---|---|---|
inicjuj(10, [1,1,1,1,2,2,2,1,1,1]) |
- | $n = 10$ |
ile_powtorzen(0, 9) |
5 | 查询整个序列 |
ile_powtorzen(0, 6) |
5 | 查询片段 $[1, 1, 1, 1, 2, 2, 2]$ |
ile_powtorzen(4, 6) |
2 | 查询片段 $[2, 2, 2]$ |
ile_powtorzen(3, 4) |
0 | 查询片段 $[1, 2]$ |
子任务
测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试组成。
令 $q$ 表示查询的总数。在所有子任务中，满足 $1 \le n \le 250\,000$，$1 \le q \le 500\,000$。
| 子任务 | 数据范围 | 分值 |
|---|---|---|
| 1 | $n, q \le 200$ | 5 |
| 2 | $n, q \le 5000$ | 10 |
| 3 | $n, q \le 20\,000$ | 10 |
| 4 | ile_powtorzen 查询中的所有片段长度相同 |
10 |
| 5 | 灯泡只有两种颜色 | 10 |
| 6 | ile_powtorzen 查询中的参数 $a$ 和 $b$ 分别是非递减的 |
5 |
| 7 | ile_powtorzen 查询中的参数 $a$ 是非递减的 |
10 |
| 8 | $n, q \le 100\,000$ | 15 |
| 9 | 无额外限制 | 25 |
实现细节
示例错误解决方案以及示例库位于 dlazaw 文件夹中。库的行为可能与评测机上的不同，且不满足任务的假设。它们仅用于展示与程序的交互方式。
假设 powgrader.cpp 文件与你的解决方案在同一文件夹中，编译命令如下：
g++ -O3 -static pow.cpp powgrader.cpp -std=c++17
这样编译的程序会从标准输入读取查询数据，并将 ile_powtorzen 的查询结果依次输出到标准输出。输入格式如下：
- 第 1 行：查询总数 $z$（包括对
inicjuj函数的调用）； - 第 2 行：字符
i，数字 $n$，随后是 $n$ 个表示连续灯泡颜色的数字； - 随后的 $z-1$ 行：字符
p，随后是描述ile_powtorzen(a, b)查询的数字 $a$ 和 $b$。