题意： 标题：递增三元组
给定三个整数数组 A = [A1, A2, … AN], B = [B1, B2, … BN], C = [C1, C2, … CN]， 请你统计有多少个三元组(i, j, k) 满足：
- 1 <= i, j, k <= N
- Ai < Bj < Ck
【输入格式】 第一行包含一个整数N。 第二行包含N个整数A1, A2, … AN。 第三行包含N个整数B1, B2, … BN。 第四行包含N个整数C1, C2, … CN。
对于30%的数据，1 <= N <= 100 对于60%的数据，1 <= N <= 1000 对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000
【输出格式】 一个整数表示答案
【样例输入】 3 1 1 1 2 2 2 3 3 3
【样例输出】 27
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 思路： 先对 a[] 与 c[] 快排一波 用an[] ,cn[]分别统计 a[]中 某元素 前（包含本身及其小于这数）的数的个数 和从c[]中某元素 后（包含本身及其大于这个数）的数的个数 在枚举 b[i] b[i]=an[d]*cn[d1] (d<b[i]<d1)
代码语言：javascript复制#include<stdio.h>
#include <string.h>
#define N 100004
long int n,anmin=0,cnmax=0,tn=0;
long int an[N],cn[N];
void swp(long int *t,long int x,long int y)
{ long int tem=t[x];
t[x]=t[y];
t[y]=tem;
}
long int qp(long int t[N],long int r,long int l)
{
long int x=t[r];
long int i=r;
long int j=l 1;
while(1)
{
while(t[ i]<x&&i<l);
while(t[--j]>x);
if(i<j)swp(t,i,j);
else break;
}
swp(t,r,j);
return j;
}
void ppp(long int *t,long int r,long int l)
{
long int m;
if(r<l)
{ m=qp(t,r,l);
ppp(t,r,m-1);
ppp(t,m 1,l);
}
}
int main()
{long int i,j,sum=0;
long int a[N],b[N],c[N];
memset(an,0,sizeof(an));
memset(cn,0,sizeof(cn));
scanf("%ld",&n);
for(i=1;i<=n;i )
{ scanf("%ld",&a[i]);
if(anmin>a[i]||i==1)anmin=a[i];
}
for(i=1;i<=n;i )
scanf("%ld",&b[i]);
for(i=1;i<=n;i )
{ scanf("%ld",&c[i]);
if(cnmax<c[i])cnmax=c[i];
}
ppp(a,1,n);
ppp(c,1,n);
for(i=1;i<=n;i )
{
if(an[a[i]])an[a[i]] ;//相同 就加一即可
else an[a[i]]=i;//通过排序后的位置得出 此数前面大的个数
j=n-i 1;
if(cn[c[j]])cn[c[j]] ;
else cn[c[j]]=n 1-j;//通过排序后的位置得出 此数后面大的个数
}
for(i=1;i<=n;i )
{ long int d=b[i]-1;
long int d1=b[i] 1;
while(an[d]==0&&d>=anmin)d--;
while(cn[d1]==0&&d1<=cnmax)d1 ;
sum =an[d]*cn[d1];
}
printf("%ldn",sum);
return 0;
}
