P9990 [Ynoi Easy Round 2023] TEST_90

You are given a sequence $a_1,\dots,a_n$ of length $n$. There are $m$ queries. In each query, given $l,r$, find how many subintervals $[i,j]$ in the interval $[l,r]$ satisfy $l\le i\le j\le r$, and the number of distinct values that have appeared in $[i,j]$ is odd.

The first line contains an integer $n$. The next line contains $n$ integers representing the sequence $a_1,\dots,a_n$. The next line contains an integer $m$. The next $m$ lines each contain two integers $l\;r$, representing a query.

For each query, output one line containing one integer, which is the answer.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. For $25\%$ of the testdata, $1\le n,m\le 10^2$. For $50\%$ of the testdata, $1\le n,m\le 10^4$. For the other $25\%$ of the testdata, the number of distinct values that appear in the sequence does not exceed $100$. For $100\%$ of the testdata, $1\le n\le 10^6$, $1\le m\le 10^6$, $1\le a_i\le n$. For each query, $1\le l\le r\le n$. All values above are integers. Translated by ChatGPT 5