（前缀和/思维）Codeforces Round ＃806 (Div. 4)F. Yet Another Problem About Pairs Satisfying an Inequality

一.题意

给你一个数组，要求你找出数组中满足 ai<i<aj<j 的数对个数。

二.思路

首先限定 数对中的每一个数一定满足ai<i，那么只需要建立一个i<aj的关系即可。

我们利用前缀和的思想 sum[i]代表  i之前包括i 所有满足ai<i的数的个数，那么sum[a[j]-1]就是所有满足i<a[j]的且满足ai<i的个数。然后枚举的时候再加上一个限定条件 a[j]<j 就行啦。

三.代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;
const int N = 2e5+10;
int a[N];
map<int,int> sum;
typedef long long LL;

void solve()
{
    int n;
    cin>>n;
    sum.clear();
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]+=sum[i-1]+(a[i]<i);//限定 a[i]<i
    }
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        if(i>a[i])res+=sum[a[i]-1];
        //if条件限定a[j]<j sum[a[i]-1]则是限定了i<a[j]这样全部符合条件的对数
    }
    cout<<res<<endl;
    
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}