2018藍橋杯省賽B組-6.遞增三元組

标題：遞增三元組

給定三個整數數組

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

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多餘内容。

注意：

main函數需要傳回0;

隻使用ANSI C/ANSI C++ 标準;

不要調用依賴于編譯環境或作業系統的特殊函數。

所有依賴的函數必須明确地在源檔案中 #include

不能通過工程設定而省略常用頭檔案。

送出程式時，注意選擇所期望的語言類型和編譯器類型。

這個題o（3n）算法，以中間的數組b為線索，分别找a，c數組符合條件的位置，求乘積和即可。

#include<cstdio>
#include<algorithm>
using namespace std;

long long n;
int a[100005],b[100005],c[100005];

int main() {
	
	scanf("%lld",&n);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
	}
	for(int i=1; i<=n; i++) {
		scanf("%d",&b[i]);
	}
	for(int i=1; i<=n; i++) {
		scanf("%d",&c[i]);
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	sort(c+1,c+1+n);
	long long sum=0;
	long long  j1=1,j2=1;
	for(int i=1; i<=n; i++) {
		while(a[j1]<b[i]&&j1<=n) {
			j1++;
		}
		while(c[j2]<=b[i]&&j2<=n) {
			j2++;
		}
		
		sum+=(j1-1)*(n-j2+1);   //至少有一個long long 保險起見隻要有long long 運算的各參數都開long long
	}
	printf("%lld",sum);
	return 0;
}