T565374 「TFXOI R1」过往与现实之历史

>时间和空间交织错落，~~「神明」~~ 与*幻影*混杂凌乱。

**注意，题目描述的末尾有形式化题意。** 「神」创造了「过往历史」。 - 「过往历史」上有 $n$ 个事件，每个事件有一个**互不相同的**值 $s_i$。 - 「时代」是「过往历史」上由任意个**连续**事件组成的区间，若某个事件的值 $s_i$ 在一个「时代」中出现了 $p$ 次，则称该事件在这个「时代」中发生了 $p$ 次。 - 当某个「时代」全部的事件在这个「时代」中都只发生了小于等于 $k$ 次，那么「神」会认为这个「时代」是「时代的骄傲」。 「神」想知道有多少个「时代」是「时代的骄傲」。 但是 ~~「神」~~ 显然对这个问题不屑一顾，因为他可以改变 $m$ 次「现实历史」。 具体而言： - 一开始，即「过往历史」被创造之际，「现实历史」也与「过往历史」相同。 - 接着，每次 ~~「神」~~ 可以选择「过往历史」中以第 $l$ 件事件为开始，第 $r$ 件事件为结尾的「时代」（你可以理解为 $[l,r]$）中发生的所有事件再次发生在「现实历史」的结尾。 ~~「神」~~ 现在想知道「现实历史」上有多少个「时代」是「时代的骄傲」。 但是，~~「神」~~ 转念一想，这个问题的答案可能太大了，而 ~~「神」~~ 又不喜欢冗长而复杂的数字。 所以 ~~「神」~~ 只希望你能告诉他 $q$ 个小问题的答案就行了。 - 具体的，~~「神」~~ 每次告诉你 $x_i,t_i$，问你以他在第 $x_i$ 次增加的「时代」上**值为** $t_i$ 的事件为开始，最长的「时代的骄傲」有多长。 - 特别的，当 $x_i=0$ 时，询问的是以一开始「现实历史」上值为 $t_i$ 的事件为开始，最长的「时代的骄傲」的长度。 - **注意，所有询问都是在 ~~「神」~~ 增加完所有的「时代」后进行的**。 ### 形式化题意 给你一个由 $n$ 个**互不相同**的整数（$s_i$）组成的序列。 然后有 $m$ 次修改，每次在这个序列**末尾**插入原始序列 $[l_i,r_i]$ 中的所有数字。 接着有 $q$ 次询问，每次询问以第 $x_i$ 次插入的区间上**值为** $t_i$ 的数字为开头的 “好序列” 最长长度。 注意，所有询问都是在插入完所有的区间后进行的。 “好序列” $[l,r]$：满足 $[l,r]$ 中所有数字出现的次数 $\le k$。

无

无

### 样例 $1$ 解释 令 $S_0$ 为「过往历史」的事件名称集合，$S_i$ 为第 $i$ 次改变后「现实历史」的事件名称集合（$i\in[1,m]$）。 一开始：$S_0= \{1,2,3,4\}$。 第一次操作后：$S_1= \{1,2,3,4,1,2\}$。 第二次操作后：$S_2= \{1,2,3,4,1,2,2,3,4\}$。 第 $0$ 次操作增加的「时代」（即「过往历史」）上名称为 $1$ 的事件为开始的最长的「时代的骄傲」是 $\{1,2,3,4\}$。 ### 样例 $2$ 解释 最终，$S_m=\{1,2,3,4,5,6,7,8,1,2,3,4,5,2,3,4,5,6,7,8,6,7,8,3,4,5,6\}$。 以第 $1$ 次增加的「时代」上名称为 $1$ 的事件为开始的最长的「时代的骄傲」是 $\{1,2,3,4,5,2,3,4,5,6,7,8,6,7,8\}$，有 $15$ 个事件。 以第 $0$ 次增加的「时代」（即一开始的「现实历史」）上名称为 $6$ 事件为开始的最长的「时代的骄傲」是 $\{6,7,8,1,2,3,4,5,2,3,4,5,6,7,8\}$，有 $15$ 个事件。 ### 数据范围 - **本题采用捆绑测试**。 - 本题**略微卡常**，请注意程序常数级别的优化。 - 对于全部数据，$1\le n,m,k\le2\times10^5$，$1\le q\le3\times10^5$，$1\le l_i\le r_i\le n$，$1\le s_i,t_i\le10^9$，详细数据范围见下表。 |Subtask 编号|$n$|$k$|$m$|$q$|空间限制|分数| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |#1|$\le200$| $=2\times10^5$|$\le200$| |$64$ MB|$10$ pts| |#2|$\le200$|$\le200$|$\le200$|$\le200$|$64$ MB|$10$ pts| |#3|$\le3\times10^3$|$=1$||$\le3\times10^3$|$64$ MB|$10$ pts| |#4|||$\le50$||$64$ MB|$15$ pts| |#5|$\le3\times10^3$|||$\le3$|$256$ MB|$15$ pts| |#6|$\le10^5$||$\le10^5$|$\le3$|$64$ MB|$20$ pts| |#7|||||$64$ MB|$20$ pts|