[数据结构与算法]1236. 递增三元组

给定三个整数数组

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

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

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

输入格式

第一行包含一个整数?N 。

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

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

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

输出格式

一个整数表示答案。

数据范围

1≤N≤1e5?
0≤Ai,Bi,Ci≤1e5?

3
1 1 1
2 2 2
3 3 3

输出样例：

27

有点小纠结，要看好边界

#include <iostream>
#include <cstring>
using namespace std;
int n;
const int N = 1e5 + 10;
int a[100010], b[100010], c[100010];
int bj[100010];
int cnt[100010];
int as[N], cs[N];
long long ans;
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++) cin >> b[i];
    for(int i = 0; i < n; i ++) cin >> c[i];

    for(int i = 0; i < n; i ++) cnt[a[i]] ++;
    bj[0] = cnt[0];//加上a为空的时候
    for(int i = 1; i < N; i ++) bj[i] = bj[i - 1] + cnt[i];
    for(int i = 0; i < n; i ++) as[i] = bj[b[i] - 1];
   
    memset(cnt, 0, sizeof cnt);
    memset(bj, 0, sizeof bj);

    for(int i = 0; i < n; i ++) cnt[c[i]] ++;
    for(int i = 1; i < N; i ++) bj[i] = bj[i - 1] + cnt[i];
    for(int i = 0; i < n; i ++) cs[i] = n - cnt[0] - bj[b[i]];//减去b为空的时候

    for(int i = 0; i < n; i ++) {
        ans += (long long)as[i] * cs[i];
    }

    cout << ans << endl;
    return 0;
}

y总的， 不纠结?

#include <iostream>
#include <cstring>
using namespace std;
int n;
const int N = 1e5 + 10;
int a[100010], b[100010], c[100010];
int bj[100010];
int cnt[100010];
int as[N], cs[N];
long long ans;
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i], a[i] ++;
    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 ++) cnt[a[i]] ++;
    for(int i = 1; i < N; i ++) bj[i] = bj[i - 1] + cnt[i];
    for(int i = 0; i < n; i ++) as[i] = bj[b[i] - 1];
    
    memset(cnt, 0, sizeof cnt);
    memset(bj, 0, sizeof bj);

    for(int i = 0; i < n; i ++) cnt[c[i]] ++;
    for(int i = 1; i < N; i ++) bj[i] = bj[i - 1] + cnt[i];
    for(int i = 0; i < n; i ++) cs[i] = bj[N - 1] - bj[b[i]];

    for(int i = 0; i < n; i ++) {
        ans += (long long)as[i] * cs[i];
    }
    
    cout << ans << endl;
    return 0;
}

#时间：几倍线性1e5，不会超

#全部和b做比较会比较好，就可以一一对应上，要不然还要找

#本来想着二分找，太麻烦，如果只是1e5的话，放在数组里找下标会简单的多，也更方便一点，顺序表查找