Rockdu's Blog

【题目描述】

给定一个有n个元素的序列，元素编号为1~n，每个元素有三个属性a,b,c，求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。

【输入格式】

第一行一个整数n，表示序列长度。

第二行n个整数，分别表示a1~an。

第三行n个整数，分别表示b1~bn。

第四行n个整数，分别表示c1~cn。

【输出格式】

一个整数，表示答案。

【样例输入】

5
1 5 3 4 2
2 5 3 4 1
1 2 5 3 4

【样例输出】

3

【样例解释】

满足条件的(i,j)共有以下三对：

(1,2)

(1,3)

(1,4)

【数据范围与约定】

对于30%的数据，n<=5000。

对于100%的数据，1<=n<=50000，保证所有的ai、bi、ci分别组成三个1~n的排列。

【来源】

HZOI 2016

练习一下CDQ分治，写了一个CDQ套CDQ。突然发现CDQ真的太好写了，别说4维了，6、7维偏序都不是问题（虽然可能还卡不过n^2）。

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
struct node {
	int id, a, b, c;
}t[maxn];
int n;
LL ans;
 
bool cmp_abc(const node &A, const node &B) {
	return A.a == B.a ? A.b == B.b ? A.c == B.c ? A.id < B.id : A.c < B.c : A.b < B.b : A.a < B.a;
}
 
bool cmp_bca(const node &A, const node &B) {
	return A.b == B.b ? A.c == B.c ? A.a == B.a ? A.id < B.id : A.a < B.a : A.c < B.c : A.b < B.b;
}
 
bool cmp_cab(const node &A, const node &B) {
	return A.c == B.c ? A.a == B.a ? A.b == B.b ? A.id < B.id : A.b < B.b : A.a < B.a : A.c < B.c;
}
 
namespace BIT {
	int tree[maxn];
	#define lowbit(x) ((x) & (-(x))) 
	void add(int x, int dt) {
		for(register int i = x; i <= n; i += lowbit(i))
			tree[i] += dt;
	}
	int query(int x) {
		int ans = 0;
		for(register int i = x; i; i -= lowbit(i))
			ans += tree[i];
		return ans;
	}
}
 
void cdq(int l, int r, int m1) {
	if(l == r) return ;
	int mid = l + r >> 1, tmp = t[mid].a;
	cdq(l, mid, m1), cdq(mid + 1, r, m1);
	sort(t + l, t + r + 1, cmp_bca);
	for(register int i = l; i <= r; ++i) {
		if(t[i].a <= tmp && t[i].id <= m1) 
			BIT::add(t[i].c, 1);
		if(t[i].a > tmp && t[i].id > m1) 
			ans += BIT::query(t[i].c - 1);
	}
	for(register int i = l; i <= r; ++i)
		if(t[i].a <= tmp && t[i].id <= m1) BIT::add(t[i].c, -1);
}
 
void CDQ(int l, int r) {
	if(l == r) return ;
	int mid = l + r >> 1;
	CDQ(l, mid), CDQ(mid + 1, r);
	sort(t + l, t + r + 1, cmp_abc);
	cdq(l, r, mid);
}
 
int main() {
	freopen("partial_order.in", "r", stdin);
	freopen("partial_order.out", "w", stdout);
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &t[i].a);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &t[i].b);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &t[i].c), t[i].id = i;
	CDQ(1, n);
	printf("%lld", ans);
	return 0;
}