资讯详情

【题目来源】

学而思编程：数对数目

【题目描述】

给定一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)。请你找出一共有多少个数对 \((i,j)\) 满足 \(a[i]\lt i\lt a[j]\lt j,1\le i,j\le n\)。

例如，长度为 \(8\) 的序列 \([1,1,2,3,8,2,1,4]\)，有 \(3\) 个满足要求的数对：\((2,4)\)、\((2,8)\)、\((3,8)\)；

1）数对 \((2,4)\) 有 \(a[2]=1,a[4]=3\) 满足 \(a[2]<2<a[4]<4\)；

2）数对 \((2,8)\) 有 \(a[2]=1,a[8]=4\) 满足 \(a[2]<2<a[8]<8\)；

3）数对 \((3,8)\) 有 \(a[3]=2,a[8]=4\) 满足 \(a[3]<3<a[8]<8\)。

【输入】

第一行，一个整数 \(n\)；
第二行，\(n\) 个整数 \(a_1,a_2,…,a_n\)​。

【输出】

一行，一个整数，表示满足要求的数对数目。

【输入样例】

8
1 1 2 3 8 2 1 4

【输出样例】

3

【核心思想】

1. 问题分析：给定长度为 \(n\) 的序列 \(a\)，求满足 \(a[i] < i < a[j] < j\) 的数对 \((i, j)\) 数量。条件可拆解为：\(i\) 需满足 \(a[i] < i\)，\(j\) 需满足 \(a[j] < j\)，且 \(i < a[j]\)。这是一个前缀和问题，核心在于固定 \(j\)，统计满足 \(a[i] < i\) 且 \(i < a[j]\) 的 \(i\) 的数量。

2. 算法选择：

   • 前缀和预处理：\(s[i]\) 表示前 \(i\) 个位置中满足 \(a[k] < k\) 的位置个数
   • 固定 \(j\) 统计：对于每个满足 \(a[j] < j\) 的 \(j\)，答案累加 \(s[a[j]-1]\)（即位置 \(1\) 到 \(a[j]-1\) 中满足 \(a[i] < i\) 的个数，这些 \(i\) 自然满足 \(i < a[j]\)）

3. 关键步骤：

   • 初始化：读取 \(n\) 和 \(a[1..n]\)
   • 前缀和预处理（\(i\) 从 \(1\) 到 \(n\)）：
     • 若 \(a[i] < i\)：\(s[i] = s[i-1] + 1\)（当前位置满足条件，计数加 \(1\)）
     • 否则：\(s[i] = s[i-1]\)（继承前一个位置的计数）
   • 统计答案（\(j\) 从 \(1\) 到 \(n\)）：
     • 若 \(a[j] < j\) 且 \(a[j] - 1 \geq 1\)：
       • \(ans += s[a[j] - 1]\)（位置 \(1\) 到 \(a[j]-1\) 中满足 \(a[i] < i\) 的个数，这些 \(i\) 满足 \(i \leq a[j]-1 < a[j]\)，即 \(i < a[j]\)）
   • 输出答案 \(ans\)

4. 时间/空间复杂度：

   • 时间复杂度：\(O(n)\)，两次线性遍历
   • 空间复杂度：\(O(n)\)，前缀和数组

5. 前缀和的核心思想：

   • 条件拆解：将 \(a[i] < i < a[j] < j\) 拆分为 \(i\) 的条件（\(a[i] < i\)）和 \(j\) 的条件（\(a[j] < j\) 且 \(i < a[j]\)），固定 \(j\) 后 \(i\) 的范围是 \([1, a[j]-1]\)
   • 前缀和快速查询：\(s[a[j]-1]\) 在 \(O(1)\) 时间内给出满足条件的 \(i\) 的数量，避免每次枚举 \(i\)
   • 边界处理：\(a[j] - 1 \geq 1\) 确保查询范围有效
   • 适用于区间统计、条件数对、双变量约束类问题

【解题思路】

【算法标签】

前缀和

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, a[2000005], s[2000005];
long long ans;
int main()
{cin >> n;for (int i=1; i<=n; i++) {scanf("%d", &a[i]);if (a[i]<i) s[i] = s[i-1]+1;  // 预处理i及之前满足a[i]<i的个数else s[i] = s[i-1];}for (int j=1; j<=n; j++) {  // 遍历n个数if (a[j]<j && a[j]-1>=1) {  // 满足a[j]<jans += s[a[j]-1];  // 并计算a[j]-1（肯定小于a[j]）坐标下满足a[a[j]-1]<(a[j]-1)的个数}}cout << ans << endl;  // 输出结果return 0;
}

【运行结果】

8
1 1 2 3 8 2 1 4
3