AcWing 1236. 递增三元组
原题链接
中等
作者:
Value
,
2020-07-08 08:37:50
,
所有人可见
,
阅读 580
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int cnt[N];
ll sa[N], sc[N];
int main(){
int n; 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] ++ ;
/* 题目特点:数据范围较小 0≤Ai,Bi,Ci≤105 */
for(int i = 0; i < n; i ++ ) cnt[a[i]] ++ ;
for(int i = 1; i < N; i ++ ) sa[i] += cnt[i] + sa[i - 1];
memset(cnt, 0, sizeof cnt);
for(int i = 0; i < n; i ++ ) cnt[c[i]] ++ ;
for(int i = N - 2; i >= 1; i -- ) sc[i] += cnt[i] + sc[i + 1];
ll res = 0;
for(int i = 0; i < n; i ++ ) res += sa[b[i] - 1] * sc[b[i] + 1];
cout << res << endl;
return 0;
}