2018年蓝桥杯B组递增三元组

题意： 标题：递增三元组

给定三个整数数组
A = [A1, A2, … AN],
B = [B1, B2, … BN],
C = [C1, C2, … CN]，
请你统计有多少个三元组(i, j, k) 满足：

1. 1 <= i, j, k <= N
2. 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)

#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)
    {
    <span class="token keyword">while</span><span class="token punctuation">(</span>t<span class="token punctuation">[</span><span class="token operator">++</span>i<span class="token punctuation">]</span><span class="token operator">&lt;</span>x<span class="token operator">&amp;&amp;</span>i<span class="token operator">&lt;</span>l<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>t<span class="token punctuation">[</span><span class="token operator">--</span>j<span class="token punctuation">]</span><span class="token operator">&gt;</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">&lt;</span>j<span class="token punctuation">)</span><span class="token function">swp</span><span class="token punctuation">(</span>t<span class="token punctuation">,</span>i<span class="token punctuation">,</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span> <span class="token keyword">break</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token function">swp</span><span class="token punctuation">(</span>t<span class="token punctuation">,</span>r<span class="token punctuation">,</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> j<span class="token punctuation">;</span>
}
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("%ld\n",sum);
return 0;
}