acwing1236. 递增三元组

题目

![image-1667832824137](https://baicai777.cn/upload/2022/11/image-1667832824137.png

题解

利用前缀和，将在a数组中比b[i]小的值有多少枚举出来得到as[]，同理，将在c数组中比b[i]大的值枚举出来得到cs[]，最后通过枚举b[i]得到答案。

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],c[N];
int cs[N],as[N];
int s[N],cnt[N];

int main(){
    cin>>n;
    //+1是因为防止后面s[b[i]-1]索引为负数
    for(int i=0;i<n;i++)scanf("%d",&a[i]),a[i]++;
    for(int i=0;i<n;i++)scanf("%d",&b[i]),b[i]++;
    for(int i=0;i<n;i++)scanf("%d",&c[i]),c[i]++;
    
    for(int i=0;i<n;i++)cnt[a[i]]++;
    for(int i=1;i<N;i++)s[i]=s[i-1]+cnt[i];
    for(int i=0;i<n;i++)as[i]=s[b[i]-1];//比b[i]小的a有多少个
    
    memset(cnt,0,sizeof cnt);
    memset(s,0,sizeof s);
    for(int i=0;i<n;i++)cnt[c[i]]++;
    for(int i=1;i<N;i++)s[i]=s[i-1]+cnt[i];
    for(int i=0;i<n;i++)cs[i]=s[N-1]-s[b[i]];//比b[i]大的c有多少个
    
    long long ans=0;
    for(int i=0;i<n;i++){
        ans+=(long long )cs[i]*as[i];
    }
    cout<<ans<<endl;
    return 0;
}