AcWing 1236. 递增三元组(前缀和方法详解)
原题链接
中等
作者:
記得_0
,
2024-03-21 10:08:30
,
所有人可见
,
阅读 3
题目描述
样例
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;//思想:遍历B[N],每次遍历找出A[N]中小于B[i]的个数a,C[N]中大于B[i]的个数c;答案就是res+=a*c;
const int N=1e5+10;
int A[N],B[N],C[N];
int ad[N],cd[N],n,cnt[N],s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&A[i]),A[i]++;
for(int i=1;i<=n;i++)scanf("%d",&B[i]),B[i]++;
for(int i=1;i<=n;i++)scanf("%d",&C[i]),C[i]++;
for(int i=1;i<=n;i++)cnt[A[i]]++;//计算出A[i]中每个数出现的个数;
for(int i=1;i<=N;i++)s[i]=s[i-1]+cnt[i];//计算前缀和,用于统计小于某个s[i]的个数;ag:s[5]代表小于等于5这个数的个数;
//为什么此处循环要从i到N,因为cnt统计的是每个数出现的个数;如果输入n为5;但
//A[5]=1000;此处要统计1000出现的次数,循环次数必须大于n;所以循环范围得足够大才能统计
//每个数出现的次数
for(int i=1;i<=n;i++)ad[i]=s[B[i]-1];//这里的意思是ad[i]存储了s中小于B[i]-1这个数的个数。
memset(cnt,0,sizeof cnt);//清空cnt,用于计算cd中每个数出现的次数;
memset(s,0,sizeof s);
for(int i=1;i<=n;i++)cnt[C[i]]++;
for(int i=1;i<=N;i++)s[i]=s[i-1]+cnt[i];
for(int i=1;i<=n;i++)cd[i]=s[N-1]-s[B[i]];
long long res(0);
for(int i=1;i<=n;i++)
{
res+=(long long)ad[i]*cd[i];
}
cout<<res;
return 0;
}