算法1 前缀和求法

递增三元组的做法1.求出在A中有多少个数小于B中的数，2.求出在C中有多少个数大于B中的数

方法1：采用前缀和 方法二：采用sort和二分

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=100010;

typedef long long LL;

int n;
int a[N],b[N],c[N];
int as[N];//表示在A中有多少个数小于b[i]
int cs[N];//表示在C中有多少个数大于b[j]

int cnt[N],s[N];//cnt数组处理每个数出现多少次,s数组处理前缀和


int main(){
  scanf("%d",&n);
  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]++;

  //求as[]
  for(int i=0;i<n;i++)cnt[a[i]]++;
  for(int i=0;i<N;i++)s[i]=s[i-1]+cnt[i];//求cnt前缀和,一定是N
  for(int i=0;i<n;i++)as[i]=s[b[i]-1];

   //求cs[] 
   memset(cnt,0,sizeof cnt);
   memset(s,0,sizeof s);
    for(int i=0;i<n;i++)cnt[c[i]]++;
    for(int i=0;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]];

    //枚举
    LL res=0;//答案可能爆int
    for(int i=0;i<n;i++)res+=(LL)as[i]*cs[i];

    cout<<res<<endl;


    return 0;
}