2024-3-2-1236-递增三元组.cpp

发表于 更新于 阅读次数： 本文字数： 949 阅读时长 ≈ 1 分钟

2024-3-2-1236-递增三元组.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstring>
#include <algorithm>
#include<cstdio>
using namespace std;
const int N = 100010;
int cnt[N],as[N],cs[N];//as[i]表示在a[]中有多少数小于b[i]
int a[N],b[N],c[N],s[N],n;//cs[i]表示在c[]中有多少数大于b[i]


int main()
{   cin>>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]++;

    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];

    //求cs[]
    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]];

    long long res=0;
    for(int i=0;i<n;i++) res+=(long long)as[i]*cs[i];/*错误实例res+=
    (long long)(as[i]*cs[i]);不需要加括号*/
    cout<<res<<endl;
    return 0;

}