P11365 [Ynoi2024] New Honkaku Magical Girl Riska

 

Given a permutation $a_1,\dots,a_n$, there are $m$ queries. In the $i$-th query, you are given $m_i$ intervals $[l_j,r_j],\;1\le j\le m_i$, satisfying $1\le l_j\le r_j\le n,\;r_j

The first line contains two integers $n,m$. The next line contains $n$ integers $a_1,\dots,a_n$. Then, for each query, the first line contains $m_i$, followed by $m_i$ lines each containing $l_j,r_j$.

Output $m$ lines. The $i$-th line should be the answer to the $i$-th query.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. Constraints: For $100\%$ of the testdata, $1\le n\le 5\times 10^5$, $1\le \sum\limits_{i=1}^m m_i\le 5\times 10^5$, $m_i\ge 1$, $1\le a_i\le n$, and all values are integers. For $0\%$ of the testdata, $n\le 10^3,\;\sum\limits_{i=1}^m m_i\le 10^3$. For another $10\%$ of the testdata, $m_i\le 10$. For another $10\%$ of the testdata, $m\le 5$. For the remaining $80\%$ of the testdata, there are no special constraints. Translated by ChatGPT 5