注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "powlib.h"。

题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Powtórzenia

每年圣诞节，Bajtazar 都会用一串五颜六色的灯链来装饰他的家。今年，Bajtazar 亲自挑选了灯链上灯泡的颜色，但他在选择时犹豫不决，最终导致灯链做得过长，显得有些冗余。

Bajtazar 的妻子在一个热门网站上读到，今年的圣诞时尚趋势要求灯链中包含尽可能多不同的重复序列。所谓重复序列，是指灯链中两个或更多连续灯泡具有相同颜色的情况。重复序列被认为是不同的，如果它们由不同颜色的灯泡组成，或者长度不同。例如，在灯链序列 $1,1,1,1,2,2,2,1,1,1$ 中（其中数字 $1$ 和 $2$ 代表不同颜色），包含了 $5$ 种不同的重复序列：

• $1,1$
• $1,1,1$
• $1,1,1,1$
• $2,2$
• $2,2,2$

Bajtazar 打算通过去掉灯链开头和/或结尾的一部分灯泡来缩短灯链，但他希望知道在进行这样的操作后，灯链中会保留多少种不同的重复序列。由于他尚未确定具体要移除多少灯泡，因此需要一个函数库，帮助他计算在不同移除方案下得到的重复序列数量。

交互方式

你的函数库需要提供以下功能：

• initiuj(n, t)
  该函数在程序开始时只会被调用一次。你可以通过它获取灯链中灯泡的总数 $n$ 以及各灯泡的颜色信息（通过向量 $t$ 提供）。灯泡颜色用从 $0$ 到 $10^{9}$ 的整数表示。灯泡编号与向量 $t$ 的索引一致，从 $0$ 到 $n-1$。

  • C++：void inicjuj(int n, vector<int> t);

• ile_powtorzen(a, b)
  调用此函数意味着询问灯链从第 $a$ 个灯泡到第 $b$ 个灯泡（包含两端，$0 \leq a \leq b < n$）这一段中，不同重复序列的数量。

  • C++：int ile_powtorzen(int a, int b);

注意你的程序不得从标准输入或文件读取任何数据，也不得向文件或标准输出写入任何内容。可以向标准错误输出（stderr）写入诊断信息，但请注意这会消耗宝贵的运行时间。不要声明 main 函数。

样例

附加样例

1. $n=10$，$q=5$，灯泡颜色为 $1,1,2,2,3,3,4,4,5,5$；
2. $n=5000$，$q=5000$，灯泡颜色为 $1,1,2,2,1,1,2,2, \ldots$；查询满足子任务 $7$ 的限制；
3. $n=245350$，$q=500000$，灯泡颜色为一个颜色 $1$，两个颜色 $2$，三个颜色 $3$，以此类推……

示例评测程序

示例错误解法及示例函数库可在「文件」中找到。这些函数库可能与评测系统中的行为不同，且不一定满足任务要求，仅用于展示程序交互方式。

编译命令如下，假设 powgrader.cpp 文件与你的解决方案位于同一目录下：

g++ -O3 -static pow.cpp powgrader.cpp -std=c++17

编译后的程序将从标准输入读取查询数据，并在标准输出中逐行输出 ile_powtorzen 查询的结果。输入格式如下：

• 第一行：查询总数 $z$（包括调用 initiuj 函数的一次）；
• 第二行：字母 i，数字 $n$，以及随后 $n$ 个数字表示各灯泡的颜色；
• 接下来的 $z-1$ 行：每行包含字母 p，以及两个数字 $a$ 和 $b$，描述一次 ile_powtorzen(a, b) 查询。

数据范围与提示

设 $q$ 为总查询数（含 inicjuj）。在所有子任务中，均满足 $1 \leq n \leq 250000$，$1 \leq q \leq 500000$。

详细子任务附加限制及分值如下表所示。