来源： 第九届蓝桥杯省赛C++B组

算法标签 枚举，二分，前缀和，双指针

题目描述

给定三个整数数组

A=[A1,A2,…AN], 
B=[B1,B2,…BN], 
C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k) 满足：

1≤i,j,k≤N
Ai<Bj<Ck

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式

一个整数表示答案。

数据范围

1≤N≤105,
0≤Ai,Bi,Ci≤105

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

对于每个b[i]而言，找到有多少a小于b，c大于b.
然后利用容斥原则，对于b而言组成递增三元组得数量有a*c组。

C++ 代码

前缀和
#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N=1e5+10;
int a[N],b[N],c[N],sa[N],sc[N],s[N];//sa是用来记录a<b[i]得前缀和，sc是用来记录c>b[i]的前缀和，s是临时数组。

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i],a[i]++;//++操作是为了防止输入为0，a[i]++使得s[a[i]]++不可能为0，使得s[i]+=s[i-1]可以计算，又因为且所有增大相当于所有不增大。
    for(int i=0;i<n;i++)cin>>b[i],b[i]++;
    for(int i=0;i<n;i++)cin>>c[i],c[i]++;

    for(int i=0;i<n;i++)s[a[i]]++;//a[i]出现数字的次数被统计。
    for(int i=1;i<N;i++)s[i]+=s[i-1];//1到i为止的出现的总次数
    for(int i=0;i<n;i++)sa[i]=s[b[i]-1];//1-b[i]的从次数

    memset(s,0,sizeof s);

    for(int i=0;i<n;i++)s[c[i]]++;
    for(int i=1;i<N;i++)s[i]+=s[i-1];
    for(int i=0;i<n;i++)sc[i]=s[N-1]-s[b[i]];//n到b[i]的总次数

    LL res=0;
    for(int i=0;i<=n;i++)res+=(LL)sa[i]*sc[i];
    cout<<res;
}