(prefix and / thinking) codeforces round 806 (Div. 4) F Yet Another Problem About Pairs Satisfying an Inequality

One . The question

Give you an array , You are required to find out the satisfaction in the array ai<i<aj<j Number to number .

Two . Ideas

First limit Every number in the number pair must satisfy ai<i, Then you only need to establish one i<aj The relationship between .

We use the idea of prefixes and sum[i] representative   i Before that includes i All satisfied ai<i The number of , that sum[a[j]-1] Is all satisfaction i<a[j] Of and satisfied with ai<i The number of . Then add a qualification when enumerating a[j]<j Just do it .

3、 ... and . Code

#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);// limit  a[i]<i
    }
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        if(i>a[i])res+=sum[a[i]-1];
        //if Condition limit a[j]<j sum[a[i]-1] Is limited i<a[j] So all qualified logarithms 
    }
    cout<<res<<endl;
    
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}