T565374 「TFXOI R1」History of Past and Present

> Time and space intertwine chaotically, ~~"deities"~~ and *illusions* mingle in disarray.

**Note: A formal problem statement is provided at the end.** The "God" created the "past history": - The "past history" contains $n$ events, each with a **distinct** value $s_i$. - An "era" is any interval of **consecutive** events from the "past history". If a value $s_i$ appears $p$ times in an "era", we say the corresponding event occurred $p$ times in that era. - An "era" is considered "pride of the era" if all events in it occur at most $k$ times. The "God" wants to know how many such "pride of the era" eras exist. However, ~~"God"~~ clearly disdains this problem because he can alter the "current history" $m$ times: - Initially, when the "past history" is created, the "current history" is identical to it. - Subsequently, each time ~~"God"~~ can select an "era" (interval $[l, r]$) from the "past history" and append all its events to the end of the "current history". ~~"God"~~ now wants to know how many "pride of the era" eras exist in the "current history". However, ~~"God"~~ realizes the answer might be too large and dislikes cumbersome numbers. Thus, ~~"God"~~ only requires you to answer $q$ small queries: - Specifically, for each query with parameters $x_i, t_i$, find the maximum length of a "pride of the era" starting from the event with value $t_i$ in the interval added during the $x_i$-th modification. - When $x_i = 0$, the query refers to the initial "current history" (before any modifications). - **All queries are processed after all modifications are completed**. ### Formal Problem Statement Given a sequence of $n$ **distinct** integers $s_i$. There are $m$ modifications: each appends all numbers from the original interval $[l_i, r_i]$ to the end of the sequence. Then process $q$ queries: for each query $(x_i, t_i)$, find the maximum length of a "good sequence" starting from the number $t_i$ in the interval inserted during the $x_i$-th modification. A "good sequence" $[l, r]$ satisfies: every number in $[l, r]$ appears at most $k$ times.

N/A

N/A

### Sample 1 Explanation Let $S_0$ be the initial "current history", and $S_i$ be the "current history" after the $i$-th modification. Initial: $S_0 = \{1, 2, 3, 4\}$. After first modification: $S_1 = \{1, 2, 3, 4, 1, 2\}$. After second modification: $S_2 = \{1, 2, 3, 4, 1, 2, 2, 3, 4\}$. The longest "pride of the era" starting from value $1$ in the $0$-th modification (initial history) is $\{1, 2, 3, 4\}$ (length 4). ### Sample 2 Explanation Final $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\}$. The longest "pride of the era" starting from value $1$ in the first modification has length 15. The longest "pride of the era" starting from value $6$ in the $0$-th modification also has length 15. ### Constraints - **Bundled testing is used**. - **Moderately tight time constraints**: optimize your code carefully. - For all data: $1 \le n, m, k \le 2 \times 10^5$, $1 \le q \le 3 \times 10^5$, $1 \le l_i \le r_i \le n$, $1 \le s_i, t_i \le 10^9$. Detailed constraints: | Subtask ID | $n$ | $k$ | $m$ | $q$ | Memory Limit | Points | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | #1 | $\le 200$ | $=2 \times 10^5$ | $\le 200$ | - | 64 MB | 10 pts | | #2 | $\le 200$ | $\le 200$ | $\le 200$ | $\le 200$ | 64 MB | 10 pts | | #3 | $\le 3 \times 10^3$ | $=1$ | - | $\le 3 \times 10^3$ | 64 MB | 10 pts | | #4 | - | - | $\le 50$ | - | 64 MB | 15 pts | | #5 | $\le 3 \times 10^3$ | - | - | $\le 3$ | 256 MB | 15 pts | | #6 | $\le 10^5$ | - | $\le 10^5$ | $\le 3$ | 64 MB | 20 pts | | #7 | - | - | - | - | 64 MB | 20 pts | Translated by DeepSeek R1