时间限制 \(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();
}
- Codeforces Inequality Satisfying Another Problemcodeforces inequality satisfying another permutation codeforces another problem another problem range query permutation another problem 1858c inversions another problem yet minimization another problem 1637d partiton another problem 1175g 题解permutation another problem 题解another problem 1870e another problem 1073g yet