Yet Another Problem About Pairs Satisfying an Inequality

题意翻译

# Yet Another Problem About Pairs Satisfying an Inequality ## 题目描述 给你一个序列$ a_1, a_2, \dots a_n $ 。请计算出满足下面条件的 $(i,j) (1 \leq i, j \leq n) $个数 。 - $ a_i < i < a_j < j $ . ## 输入格式 第一行包含一个整数 $ t $ ( $ 1 \leq t \leq 1000 $ ) — 测试数据的个数 每一个测试数据的第一行包含一个整数 $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — 序列的长度 每一个测试数据的第二行包含$ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 0 \leq a_i \leq 10^9 $ ) — 序列里的元素 保证每一个测试数据的$ n $ 的总和不超过 $ 2 \cdot 10^5 $ . ## 输出格式 对于每一个测试数据，输出一个整数——满足题目条件的$(i,j)$个数 请注意，对于某些测试数据，他的答案可能会超过32位的整数，所以你应该使用64位的整数在你的编程语言里，比如说C++中的long long ## 样例 #1 ### 样例输入 #1 ``` 5 8 1 1 2 3 8 2 1 4 2 1 2 10 0 2 1 6 3 4 1 2 8 3 2 1 1000000000 3 0 1000000000 2 ``` ### 样例输出 #1 ``` 3 0 10 0 1 ``` ## 提示 对于第一组测试数据，满足条件的 $ (i, j) $ = $ \{(2, 4), (2, 8), (3, 8)\} $ . - $ (2, 4) $ 满足条件是因为 $ a_2 = 1 $ , $ a_4 = 3 $ 且$ 1 < 2 < 3 < 4 $ . - $ (2, 8) $ 满足条件是因为$ a_2 = 1 $ , $ a_8 = 4 $ 且 $ 1 < 2 < 4 < 8 $ . - $ (3, 8) $ 满足条件是因为$ a_3 = 2 $ , $ a_8 = 4 $ 且 $ 2 < 3 < 4 < 8 $ .

题目描述

You are given an array $ a_1, a_2, \dots a_n $ . Count the number of pairs of indices $ 1 \leq i, j \leq n $ such that $ a_i < i < a_j < j $ .

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — the length of the array. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \leq a_i \leq 10^9 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output a single integer — the number of pairs of indices satisfying the condition in the statement. Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

输入输出样例

输入样例 #1

5
8
1 1 2 3 8 2 1 4
2
1 2
10
0 2 1 6 3 4 1 2 8 3
2
1 1000000000
3
0 1000000000 2

输出样例 #1

3
0
10
0
1

说明

For the first test cases the pairs are $ (i, j) $ = $ \{(2, 4), (2, 8), (3, 8)\} $ . - The pair $ (2, 4) $ is true because $ a_2 = 1 $ , $ a_4 = 3 $ and $ 1 < 2 < 3 < 4 $ . - The pair $ (2, 8) $ is true because $ a_2 = 1 $ , $ a_8 = 4 $ and $ 1 < 2 < 4 < 8 $ . - The pair $ (3, 8) $ is true because $ a_3 = 2 $ , $ a_8 = 4 $ and $ 2 < 3 < 4 < 8 $ .

**题目大意**：

给定一个序列 $ a_1, a_2, \dots, a_n $，计算满足条件 $ a_i < i < a_j < j $ 的不同索引对 $(i, j)$ （其中 $1 \leq i, j \leq n$）的数量。

**输入数据格式**：

- 第一行包含一个整数 $ t $ （$ 1 \leq t \leq 1000 $）——测试数据的数量。
- 每一个测试数据的第一行包含一个整数 $ n $ （$ 2 \leq n \leq 2 \cdot 10^5 $）——序列的长度。
- 每一个测试数据的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ （$ 0 \leq a_i \leq 10^9 $）——序列里的元素。
- 保证所有测试数据的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。

**输出数据格式**：

- 对于每一个测试数据，输出一个整数——满足题目条件的 $(i,j)$ 对的数量。

请注意，对于某些测试数据，答案可能会超过32位的整数范围，因此应该使用64位整数类型（例如C++中的 long long）。

**样例 #1**：

**输入 #1**：

```
5
8
1 1 2 3 8 2 1 4
2
1 2
10
0 2 1 6 3 4 1 2 8 3
2
1 1000000000
3
0 1000000000 2
```

**输出 #1**：

```
3
0
10
0
1
```

对于第一组测试数据，满足条件的 $ (i, j) $ 对为 $ \{(2, 4), (2, 8), (3, 8)\} $。

- $ (2, 4) $ 满足条件是因为 $ a_2 = 1 $，$ a_4 = 3 $ 且 $ 1 < 2 < 3 < 4 $。
- $ (2, 8) $ 满足条件是因为 $ a_2 = 1 $，$ a_8 = 4 $ 且 $ 1 < 2 < 4 < 8 $。
- $ (3, 8) $ 满足条件是因为 $ a_3 = 2 $，$ a_8 = 4 $ 且 $ 2 < 3 < 4 < 8 $。**题目大意**： 给定一个序列 $ a_1, a_2, \dots, a_n $，计算满足条件 $ a_i < i < a_j < j $ 的不同索引对 $(i, j)$ （其中 $1 \leq i, j \leq n$）的数量。 **输入数据格式**： - 第一行包含一个整数 $ t $ （$ 1 \leq t \leq 1000 $）——测试数据的数量。 - 每一个测试数据的第一行包含一个整数 $ n $ （$ 2 \leq n \leq 2 \cdot 10^5 $）——序列的长度。 - 每一个测试数据的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ （$ 0 \leq a_i \leq 10^9 $）——序列里的元素。 - 保证所有测试数据的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出数据格式**： - 对于每一个测试数据，输出一个整数——满足题目条件的 $(i,j)$ 对的数量。 请注意，对于某些测试数据，答案可能会超过32位的整数范围，因此应该使用64位整数类型（例如C++中的 long long）。 **样例 #1**： **输入 #1**： ``` 5 8 1 1 2 3 8 2 1 4 2 1 2 10 0 2 1 6 3 4 1 2 8 3 2 1 1000000000 3 0 1000000000 2 ``` **输出 #1**： ``` 3 0 10 0 1 ``` 对于第一组测试数据，满足条件的 $ (i, j) $ 对为 $ \{(2, 4), (2, 8), (3, 8)\} $。 - $ (2, 4) $ 满足条件是因为 $ a_2 = 1 $，$ a_4 = 3 $ 且 $ 1 < 2 < 3 < 4 $。 - $ (2, 8) $ 满足条件是因为 $ a_2 = 1 $，$ a_8 = 4 $ 且 $ 1 < 2 < 4 < 8 $。 - $ (3, 8) $ 满足条件是因为 $ a_3 = 2 $，$ a_8 = 4 $ 且 $ 2 < 3 < 4 < 8 $。