AcWing 1236. 递增三元组(桶排序+前缀和)
原题链接
中等
作者:
Bear_King
,
2021-01-15 11:11:28
,
所有人可见
,
阅读 514
递增三元组
这道题一眼望去,直接暴力破解 -> O(n^3) 容易超时拿不到全分
本题可行方法:
1、排列+二分
2、模拟+前缀和
3、双指针性质优化
因为本题数据规模相对理想,而且c数组的限制明确
因此,可以尝试用:桶排序+前缀和
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
typedef long long LL;//防止越界
int n;
int a[N],b[N],c[N];
int as[N];//表示在a中有多少个数,小于b[i]
int cs[N];//表示在c中有多少个数,大于b[i]
int cnt[N],s[N];//模拟
int main()
{
cin>>n;
//因为要预处理as,cs数组所以要保证a,b,c数组向后偏移防止越界
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]++;
//处理as数组
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];
//处理前缀和之后,要统计归位需要还原(加-1),拿出在s里面所有小于b[i]的总和
//回收再利用
memset(cnt,0,sizeof cnt);
memset(s,0,sizeof s);
//处理cs数组
for(int i = 0;i < n;i ++) cnt[c[i]] ++;
for(int i = 1;i < N;i ++) s[i] = s[i-1] + cnt[i];//因为要整理c数组大于b的值最大不能超过N
for(int i = 0;i < n;i ++) cs[i] = s[N-1] - s[b[i]];
//N的前缀和-b数组值的前缀和=c数组小于b[i]的个数总和
//累加所有三元组情况
LL res = 0;
for(int i = 0;i < n;i ++) res += (LL)as[i]*cs[i];
cout<<res<<endl;
return 0;
}