数据前缀：aurora。

CodeForces-1935D

题目描述

给定大小为 $n$ 的集合 $S=\{s_1,\dots,s_n\}$ 和整数 $c$，满足 $0\le s_i\le c$。统计整数对 $(x,y)$ 的数量，满足

$$0\le x\le y\le c,\quad x+y\notin S,\quad y-x\notin S.$$

输入格式

本题包含多组测试数据。

第一行一个整数 $T$（$1\le T\le 2\times 10^4$），表示测试用例数。

对于每组测试用例：

• 第一行两个整数 $n,c$（$1\le n\le 3\times10^5$，$1\le c\le 10^9$）；
• 第二行 $n$ 个整数 $s_1,\dots,s_n$（$0\le s_1 < s_2 < \dots < s_n\le c$）。

保证所有测试用例的 $\sum n \le 3\times10^5$。

输出格式

对每组测试用例输出一行一个整数，表示满足条件的整数对数量。答案可能超过 32 位，请使用 64 位整数。

输入输出样例

样例 #1

样例输入 #1

8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353

样例输出 #1

3
16139
10
2
33
36
35
499999998999122959

样例 #2

样例输入 #2

3
1 1
0
1 5
0
2 10
2 8

样例输出 #2

1
15
50

样例 #3

样例输入 #3

2
4 10
2 4 6 7
3 1000000000
228 1337 998244353

样例输出 #3

35
499999998999122959

样例 #4

样例输入 #4

6
13 12
0 1 2 3 4 5 6 7 8 9 10 11 12
16 30
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
15 30
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
9 100
0 1 2 49 50 51 98 99 100
11 1000000000
0 1 2 123456789 499999999 500000000 500000001 876543210 999999998 999999999 1000000000
6 999999999
123456788 123456789 246913578 500000000 876543210 999999998

样例输出 #4

0
240
256
4485
499999993250000017
499999995935185192

说明/提示

样例 1 第一组数据中满足条件的对为 $(0,0),(2,2),(3,3)$。

数据范围

• $1\le T\le 2\times10^4$，$1\le c\le 10^9$，$\sum n\le 3\times10^5$，$n\le c+1$。
• 本题共 $100$ 个测试点。

$$ \begin{array}{|c|l|} \hline \text{测试点} & \text{性质} \\ \hline 1\sim5 & T \le 5\text{，}\sum c\le 10\text{，}n\le 3 \\ 6\sim12 & T \le 5\text{，}\sum c\le 100\text{，}n\le 5 \\ 13\sim21 & T \le 5\text{，}\sum c\le 1000\text{，}n\le 100 \\ 22\sim40 & n\le 100\text{，}\sum n\le 350\text{, }c \le 10^5 \\ 41\sim56 & n\le 2000\text{，}\sum n\le 5000 \\ 57\sim70 & S\text{ 中所有元素奇偶性相同} \\ 71\sim75 & S=\{0,1,\dots,n-1\}\text{ 或 }S=\{c-n+1,\dots,c\} \\ 76\sim80 & 0\in S\text{ 且 }c\in S \\ 81\sim100 & \sum n \le 3\times10^5 \\ \hline \end{array} $$

背景（与题目没有任何关系）

贡献说明

OpenAI Codex 协助补充样例与说明，核对新增样例答案，并完成输入合法性检查及测评数据包校验。