Codeforces Round #806 (Div. 4) ---F Yet Another Problem About Pairs Satisfying an Inequality

题目链接：Problem - 1703F - Codeforces

题意：一数组arr[]  中 arr[i] < i < arr[j] < j ; 的情况有多少种？

题解：垃圾思想：暴力 j 并对从 1 ~ j  看看有没有 i 符合 arr[i] < i < arr[j] < j （个P的）;

           高级思想：发现利用前缀和 的价值；

#include <iostream>
using namespace std;
const int maxn = (int)2e5 + 5;
int a[maxn];
int b[maxn];
void solve()
{
int n; cin >> n;
long long
ans = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (i - 1 >= 0)
{
b[i] = b[i - 1] + (a[i] < i);//
把前j项 符合 a[i]<i 的个数累加起来
}
if(a[i]>=2&& a[i]<i) // 对吧
ans += b[a[i]-1];
}
cout << ans << endl;
}
int main()
{
int t; cin >> t;
while (t--)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
solve();
}
return 0;
}

最后

以上就是无情魔镜为你收集整理的Codeforces Round #806 (Div. 4) ---F Yet Another Problem About Pairs Satisfying an Inequality的全部内容，希望文章能够帮你解决Codeforces Round #806 (Div. 4) ---F Yet Another Problem About Pairs Satisfying an Inequality所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。