[Ynoi Easy Round 2023] TEST_90

Luogu
IDLGP9990
Time3000ms
Memory512MB
DifficultyP6
2023O2优化Ynoi
给定一个长度 $n$ 的序列 $a_1,\dots,a_n$。 共有 $m$ 次询问,每次询问给定 $l,r$,求区间 $[l,r]$ 中有多少 子区间 $[i,j]$ 满足 $l\le i\le j\le r$,且在区间 $[i,j]$ 内出现过的数的个数为奇数。 ## Input 第一行一个整数 $n$。 接下来一行 $n$ 个整数表示序列 $a_1,\dots,a_n$ 接下来一行一个整数 $m$。 接下来 $m$ 行,每行两个整数 $l\;r$ 表示一个询问。 ## Output 对每个询问,输出一行,包含一个整数,表示答案。 [samples] ## Note Idea:nzhtl1477,Solution:ccz181078,Code:ccz181078,Data:ccz181078 对于 $25\%$ 的数据,满足 $1\le n,m\le 10^2$。 对于 $50\%$ 的数据,满足 $1\le n,m\le 10^4$。 对于另外 $25\%$ 的数据,满足序列中出现过的数个数不超过 $100$。 对于 $100\%$ 的数据,满足 $1\le n\le 10^6$,$1\le m\le 10^6$,$1\le a_i\le n。$ 对每个询问满足 $1\le l\le r\le n$。 以上所有数值为整数。
Samples
Input #1
5
2 3 5 1 5
5
2 3
1 1
1 3
2 5
2 4
Output #1
2
1
4
6
4
Input #2
10
2 8 5 1 10 5 9 9 3 5
10
6 8
1 2
3 5
5 7
1 7
3 9
4 9
1 4
3 7
2 5
Output #2
4
2
4
4
16
16
12
6
9
6
API Response (JSON)
{
  "problem": {
    "name": "[Ynoi Easy Round 2023] TEST_90",
    "description": {
      "content": "给定一个长度 $n$ 的序列 $a_1,\\dots,a_n$。 共有 $m$ 次询问,每次询问给定 $l,r$,求区间 $[l,r]$ 中有多少 子区间 $[i,j]$ 满足 $l\\le i\\le j\\le r$,且在区间 $[i,j]$ 内出现过的数的个数为奇数。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9990"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度 $n$ 的序列 $a_1,\\dots,a_n$。\n\n共有 $m$ 次询问,每次询问给定 $l,r$,求区间 $[l,r]$ 中有多少 子区间 $[i,j]$ 满足 $l\\le i\\le j\\le r$,且在区间 $[i,j]$ 内出现过的数的个数为奇数。\n\n## Input\n\n第一行一个整数 $n$。\n\n接下来一行 $n$ 个整数表示序列 $a_1,\\dots,a_n$\n\n接下来一行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments