递增三元组（蓝桥杯18F）

暴力求解：

#include<iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	int* A = new int[N];
	int* B = new int[N];
	int* C = new int[N];
	for (int i = 0; i < N;i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	int cnt = 0;
	for (int i = 0; i < N;i++) {
		for (int j = 0; j < N; j++) {
			for (int z = 0; z < N; z++) {
				if (A[i]<B[j]<C[z]) {
					cnt++;
				}
			}
		}
	}
	cout << cnt;
	return 0;
}

优化排序加二分查找：

#include<iostream>
using namespace std;
void Qsort(int arr[], int L, int R) {
	if (L >= R) {
		return;
	}
	int left = L, right = R, key = arr[L], flag = 0;
	while (left < right) {
		if (flag == 0) {
			if (arr[right] < key) {
				arr[left] = arr[right];
				left++;
				flag = 1;
			}
			else {
				right--;
			}
		}
		else if (flag == 1) {
			if (arr[left] > key) {
				arr[right] = arr[left];
				right--;
				flag = 0;
			}
			else {
				left++;
			}
		}
	}
	arr[left] = key;
	Qsort(arr, L, left - 1);
	Qsort(arr, left + 1, R);
}
int tSearch_min(int* arr,int left,int right,int key, int tag) {
	if (tag == 0 && left>right) {
		return left;
	}
	else if(tag == 1 && left>right) {
		return left;
	}
	int mid = (left + right) / 2;
	if (key < arr[mid]) {
		return tSearch_min(arr, left, mid - 1, key, 0);
	}
	else if (key>arr[mid]) {
		return tSearch_min(arr, mid + 1, right, key, 1);
	}
	else {
		int i;
		for (i = mid; i >= left;i--) {
			if (arr[i] < key ) {
				return (i + 1);
			}
		}
		return (i + 1);
	}
}
int tSearch_max(int* arr, int left, int right, int key, int tag) {
	if (tag == 0 && left > right) {
		return left;
	}
	else if (tag == 1 && left > right) {
		return left;
	}
	int mid = (left + right) / 2;
	if (key < arr[mid]) {
		return tSearch_max(arr, left, mid - 1, key, 0);
	}
	else if (key > arr[mid]) {
		return tSearch_max(arr, mid + 1, right, key, 1);
	}
	else {
		int i;
		for (i = mid; i <= right; i++) {
			if (arr[i] > key) {
				return i;
			}
		}
		return i;
	}
}
int main() {
	int N;
	cin >> N;
	int* A = new int[N];
	int* B = new int[N];
	int* C = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	Qsort(A, 0, N - 1);
	Qsort(B, 0, N - 1);
	Qsort(C, 0, N - 1);
	int cnt = 0;
	for (int i = 0; i < N;i++) {
		int key = B[i];
		int min = tSearch_min(A, 0, N - 1, key, 0);
		int max = N - tSearch_max(C, 0, N - 1, key, 0);
		cnt += (min*max);
	}
	cout << cnt;
	return 0;
}