（枚举）（模拟）（前缀和）（数组模拟哈希）（可二分）1236. 递增三元组

目录

题目链接

一些话

流程

套路

ac代码

---

题目链接

1236. 递增三元组 - AcWing题库

---

一些话

int f[N];

memset(f,0,sizeof f)影响不到f[N]

所以尽量不要对f[N]赋值，不要用f[N]操作

---

流程

//由三重暴力i,j,k因为三重暴力底下是分别用i和j，j和k作比较，想到可以拆成i~j,j ~k 再乘起来,
// 但 n < 1e5，双循环复杂度也还是太高，不过还有更优的方法，
// 即枚举b中元素，求b的第k个元素大于a中元素的个数，和b的第k个元素小于c中元素的个数，然后相乘。可以通过前缀和+哈希或二分来实现
// 前缀和+哈希要先统计a和c的元素个数，然后通过前缀和来得到a和c中小于等于某值的元素个数的数组，
// 然后求b的第k个元素大于a中元素的个数就是这个a中小于等于b[k] -1 的元素个数，即s[b[k] - 1]
//b的第k个元素小于c中元素的个数就是c中元素的个数减去c中小于等于b的第k个元素的个数，即s[N-1] - s[b[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];

---

ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N],c[N],cc[N],ca[N],cnt[N],s[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]++;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++) ca[i] = s[b[i]-1];memset(s,0,sizeof s);memset(cnt,0,sizeof cnt);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++) cc[i] = s[N-1] - s[b[i]];long long ans = 0;for(int i = 0;i < n;i++){ans += ca[i] * (long long) cc[i];}cout << ans << endl;return 0;
}

---