P16383 [IATI 2025] Self-describing

Elena is yet again tasked with solving a problem involving subarrays with a special property. By now she finds these tasks banal, so she leaves writing a solution to you -- the IATI contestants. The problem statement is as follows: We define a "self-describing" array $b_0, b_1, \dots, b_{M-1}$ -- an array in which for all $b_i$ it is true that the number $b_i$ appears $\textit{exactly}$ $b_i$ times in the entire array. $[1, 2, 2]$, $[5,5,5,5,5]$, $[3,1,3,2,3,2]$ are all examples of "self-describing" arrays, while $[100, 1, 2, 2]$ (there is only one occurrence of $100$), $[1,1,1,1,1]$ (there are $5$ occurrences of $1$) are all examples of non-"self-describing" arrays. Additionally for an array $b_0, b_1, \dots, b_{M-1}$ we define a "self-describing" subarray as a subarray $b_l, b_{l+1} \dots b_r$ that is itself "self-describing". You are given an array $a_0, a_1, \dots, a_{N-1}$ and $Q$ queries $(l,r)$ such that $l \leq r$. For each query you should find the number of "self-describing" subarrays $(l', r')$ for which $l \leq l' \leq r' \leq r$ for all queries. ### Implementation details You should implement the following two procedures: ```cpp void init(int N, int Q, const std::vector& a) ``` This function will be called once per test and provides your program with the original array as a vector, consisting of the $N$ values $a_0, a_1, \dots a_{N-1}$ in this order. ```cpp long long query(int l, int r) ``` This function will be called $Q$ times per test and will correspond to a query for the range $(l, r)$, it should return the answer to that query. ### Local testing To test your program locally, a local grader and a header file are provided. The local grader reads $N$, $Q$, $a_1, a_2, \dots, a_N$ and $Q$ queries $(l, r)$ in this order, calls your $\verb|init|$ and then outputs the answers your program gave to all $\verb|query|$ calls. You are free to modify the local grader.

N/A

N/A

### Constraints - $1 \leq N, Q \leq 3 \times 10^5$ - $1 \leq a_i \leq N$ for all $0 \leq i \leq N - 1$ - $0 \leq l \leq r \leq N - 1$ for all queries. ### Subtasks | **Subtask** | **Points** | **Necessary subtasks** | **$N$** | **$Q$** | **Other constraints** | | :---: | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $-$ | $-$ | $-$ | Example. | | $1$ | $6$ | $-$ | $\leq 500$ | $=1$ | The only query is $[1, N]$. | | $2$ | $6$ | $1$ | $\leq 5000$ | $=1$ | ^ | | $3$ | $39$ | $1-2$ | $\leq 3\times 10^5$ | $=1$ | ^ | | $4$ | $11$ | $0-3$ | $\leq 3\times 10^5$ | $\leq 500$ | | | $5$ | $16$ | $0-4$ | $\leq 3 \times 10^5$ | $\leq 5\times10^4$ | $-$ | | $6$ | $22$ | $0-5$ | $\leq 3\times10^5$ | $\leq 5\times10^5$ | $-$ | The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.