P10264 [GESP202403 Level 8] Connecting Bamboo Poles

Related multiple-choice and true/false problems: .

Student Xiao Yang wants to play a card game called “Connecting Bamboo Poles”. The rules are as follows: each card has a value $v$. The given cards are placed one by one at the end of a queue of cards. If, before placing a card, there is already a card in the queue with the same value as this card, then Xiao Yang will remove from the queue all cards between these two cards (including the two cards themselves). Xiao Yang now has a card sequence $A$ of length $n$, where the value of each card is $A_i$ ($1\le i\le n$). Xiao Yang has $q$ queries. In the $i$-th query ($1\le i\le q$), Xiao Yang gives $l_i,r_i$. Xiao Yang wants to know: if we play “Connecting Bamboo Poles” using all cards with indices in $[l_i,r_i]$ in increasing index order, how many cards remain in the queue at the end.

One line contains a positive integer $T$, the number of test cases. For each test case, the first line contains a positive integer $n$, the length of the card sequence $A$. The second line contains $n$ positive integers $A_1,A_2,\dots,A_n$, the values of the cards in $A$. The third line contains a positive integer $q$, the number of queries. The next $q$ lines each contain two positive integers $l_i,r_i$, describing a query.

For each test case, output $q$ lines. The $i$-th line ($1\le i\le q$) outputs a non-negative integer, which is the answer to the $i$-th query.

**Sample Explanation** For the first query, Xiao Yang places the cards in the order $1,2,2$. When placing the last card, the two cards with value $2$ are removed, so only one card with value $1$ remains in the queue. For the second query, the queue changes as follows: $\{\}\to\{1\}\to\{1,2\}\to\{1,2,2\}\to\{1\}\to\{1,3\}\to\{1,3,1\}\to\{\}\to\{3\}$. Therefore, in the end only one card with value $3$ remains in the queue. **Constraints** |Subtask|Score|$T$|$n$|$q$|$\max A_i$|Special Condition| |:---:|:---:|:---:|:---:|:---:|:---:|:---:| |$1$|$30$|$\le 5$|$\le100$|$\le100$|$\le13$| |$2$|$30$|$\le 5$|$\le 1.5\times10^4$|$\le 1.5\times10^4$|$\le13$|For all queries, the right endpoint equals $n$. |$3$|$40$|$\le 5$|$\le 1.5\times10^4$|$\le 1.5\times10^4$|$\le13$| For all testdata, it is guaranteed that $1\le T\le 5$, $1\le n\le 1.5\times 10^4$, $1\le q\le 1.5\times 10^4$, and $1\le A_i\le 13$. Translated by ChatGPT 5