[Codeforces] CF1703F Yet Another Problem About Pairs Satisfying an Inequality

时间限制 \(2s\) | 空间限制 \(250M\)

题目描述

给你一个序列$ 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

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 $ .

题解

使\(f_i\)表示在\(j\in [i,n]\)，有多少个满足\(a_j<j\)的，那么当找到一个\(a_i<i\)时，就可以让答案加上\(f_{i+1}\)，这里需要注意，因为\(f_i\)可能会把\(a_i\)本身也算进去，所以需要加上\(f_{i+1}\)而不是\(f_i\)

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
int n,ans;
int a[Maxn],f[Maxn];
void run()
{
	cin>>n;ans=0;memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) if(a[i]<i) f[a[i]]++;
	for(int i=n;i>=1;i--) f[i]+=f[i+1];
	for(int i=1;i<=n;i++) if(a[i]<i) ans+=f[i+1];
	cout<<ans<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--) run();
}