English · Original
Chinese · Translation
Formal · Original
The difference between easy and hard version are the constraints on n
You are given an array of $n$ integers (a1, a2, a3, ....... an)
You have to find the number of pairs such that a[i] xor a[j] = a[i]
First line has a single integer $t$, number of tests [1 <= $t$ <= 1000]
First line of each test has a single integer $n$, size of array [1 <= $n$ <= 1e5]
Second line of each test has $n$ integers, the array elements [0 <= $a [ i ]$ <= 1e9]
It is guaranteed that sum of n among all tests do not exceed 1e5
For each test, print a single integer, the number of pairs
## Input
First line has a single integer $t$, number of tests [1 <= $t$ <= 1000]First line of each test has a single integer $n$, size of array [1 <= $n$ <= 1e5]Second line of each test has $n$ integers, the array elements [0 <= $a [ i ]$ <= 1e9]It is guaranteed that sum of n among all tests do not exceed 1e5
## Output
For each test, print a single integer, the number of pairs
[samples]
[{"iden":"statement","content":"_Biodiverse Subsequence 和 Biodiverse Subarray 的问题陈述几乎完全相同，区别仅在于所采样的珊瑚必须构成给定序列的_子序列_还是_子数组_。尽管如此，这两个问题是截然不同的。_\n\n生物多样性是任何生态系统中最重要的特性之一，无论是在森林、红树林还是海洋中。菲律宾拥有大量该国特有的动植物物种。Cindy 是一位热衷于潜水的爱好者，她随同一群生物学家前往韦尔德岛通道，采集一些珊瑚物种用于研究。当然，所选择的样本必须准确反映珊瑚三角区海洋生物的多样性。\n\n他们发现了一排 $N$ 个珊瑚，并从中识别出 $K$ 种不同的物种。我们将此建模为一个由 $N$ 个正整数 $A_1, A_2, dots.h, A_N$ 组成的序列。从 $1$ 到 $K$ 的每个整数至少出现一次，且序列中仅出现这些整数。如果一个数字序列中从 $1$ 到 $K$ 的每个整数都至少出现一次，则称该序列为 _biodiverse_（生物多样）的。\n\n为了保护栖息地的特性，研究人员必须选择一个生物多样性的 _子数组_ 进行采样。子数组是指一个 _连续_ 的元素子序列 $A_l, A_(l + 1), dots.h A_r$，其中 $1 lt.eq l lt.eq r lt.eq N$。为了决定采样哪些珊瑚，研究人员请 Cindy 计算序列 $A$ 中生物多样性子数组的数量。\n\n帮助 Cindy 吧？\n\n输入的第一行包含两个用空格分隔的整数 $N$ 和 $K$，分别表示珊瑚的数量和不同物种的数量。\n\n第二行输入包含 $N$ 个用空格分隔的整数 $A_1$, $A_2$, $dots.h.c$, $A_N$，其中 $A_i$ 表示第 $i$ 个珊瑚的物种。\n\n请输出一行，包含一个整数，表示 $A$ 中生物多样性子数组的数量。\n\n$1 lt.eq K lt.eq N lt.eq 2 dot.op 10^5$\n\n$1 lt.eq A_i lt.eq K$ 对所有 $i$ 成立。\n\n对于所有从 $1$ 到 $K$ 的 $k$，都存在某个 $i$ 使得 $A_i = k$。\n\n*子任务 1*（40 分）：\n\n$N lt.eq 100$\n\n*子任务 2*（20 分）：\n\n$N lt.eq 2000$\n\n*子任务 3*（20 分）：\n\n$K lt.eq 2$\n\n*子任务 4*（20 分）：\n\n无其他限制。\n\n下图展示了第一个样例测试用例中研究人员可选择的六个生物多样性子数组。 \n\n"},{"iden":"input","content":"输入的第一行包含两个用空格分隔的整数 $N$ 和 $K$，分别表示珊瑚的数量和不同物种的数量。第二行输入包含 $N$ 个用空格分隔的整数 $A_1$, $A_2$, $dots.h.c$, $A_N$，其中 $A_i$ 表示第 $i$ 个珊瑚的物种。"},{"iden":"output","content":"请输出一行，包含一个整数，表示 $A$ 中生物多样性子数组的数量。"},{"iden":"scoring","content":"$1 lt.eq K lt.eq N lt.eq 2 dot.op 10^5$$1 lt.eq A_i lt.eq K$ 对所有 $i$ 成立。对于所有从 $1$ 到 $K$ 的 $k$，都存在某个 $i$ 使得 $A_i = k$。*子任务 1*（40 分）：$N lt.eq 100$*子任务 2*（20 分）：$N lt.eq 2000$*子任务 3*（20 分）：$K lt.eq 2$*子任务 4*（20 分）：无其他限制。"},{"iden":"examples","content":"输入\n4 2\n1 2 1 2\n输出\n6\n输入\n14 9\n3 1 4 1 5 9 2 6 5 3 5 8 9 7\n输出\n3\n"},{"iden":"note","content":"下图展示了第一个样例测试用例中研究人员可选择的六个生物多样性子数组。 下图展示了第二个样例测试用例中研究人员可选择的三个生物多样性子数组。 "}]}
**Definitions**
Let $ N, K \in \mathbb{Z}^+ $ with $ 1 \leq K \leq N \leq 2 \cdot 10^5 $.
Let $ A = (A_1, A_2, \dots, A_N) $ be a sequence of integers where $ A_i \in \{1, 2, \dots, K\} $, and each integer from $ 1 $ to $ K $ appears at least once.
A **biodiverse subarray** is a contiguous subarray $ A[l:r] = (A_l, A_{l+1}, \dots, A_r) $ with $ 1 \leq l \leq r \leq N $, such that the set $ \{A_l, A_{l+1}, \dots, A_r\} $ contains all integers from $ 1 $ to $ K $.
**Constraints**
1. $ 1 \leq K \leq N \leq 2 \cdot 10^5 $
2. $ 1 \leq A_i \leq K $ for all $ i \in \{1, \dots, N\} $
3. $ \forall k \in \{1, \dots, K\}, \exists i \in \{1, \dots, N\} $ such that $ A_i = k $
**Objective**
Compute the number of subarrays $ A[l:r] $ that are biodiverse, i.e.,
$$
\left| \left\{ (l, r) \mid 1 \leq l \leq r \leq N, \ \{A_l, A_{l+1}, \dots, A_r\} = \{1, 2, \dots, K\} \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "B2. Xor Pairs (Hard Version)",
"description": {
"content": "The difference between easy and hard version are the constraints on n You are given an array of $n$ integers (a1, a2, a3, ....... an) You have to find the number of pairs such that a[i] xor a[j] = a",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFB2"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The difference between easy and hard version are the constraints on n\n\nYou are given an array of $n$ integers (a1, a2, a3, ....... an)\n\nYou have to find the number of pairs such that a[i] xor a[j] = a...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"_Biodiverse Subsequence 和 Biodiverse Subarray 的问题陈述几乎完全相同，区别仅在于所采样的珊瑚必须构成给定序列的_子序列_还是_子数组_。尽管如此，这两个问题是截然不同的。_\\n\\n生物多样性是任何生态系统中最重要的特性之一，无论是在森林、红树林还是海洋中。菲律宾拥有大量该国特有的动植物物种...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ N, K \\in \\mathbb{Z}^+ $ with $ 1 \\leq K \\leq N \\leq 2 \\cdot 10^5 $. \nLet $ A = (A_1, A_2, \\dots, A_N) $ be a sequence of integers where $ A_i \\in \\{1, 2, \\dots, K\\} $, and eac...",
"is_translate": false,
"language": "Formal"
}
]
}