2018年第九届蓝桥杯省赛 递增三元组------------------C语言——菜鸟级

题意： 标题：递增三元组

  原文         欢迎访问我的博客

给定三个整数数组 

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)

复杂度 大概为 2*n*lg(n)+n

#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("%ld\n",sum);
        return 0;
}