COGS 2479. [HZOI 2016]偏序
? 解题记录 ? ? 杂OJ ? ? cdq分治 ?    2018-07-13 23:28:09    817    0    0

【题目描述】

给定一个有n个元素的序列,元素编号为1~n,每个元素有三个属性a,b,c,求序列中满足i<jai<ajbi<bjci<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,保证所有的aibici分别组成三个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;
}


上一篇: HDU5868 Different Circle Permutation

下一篇: AGC021 E - Ball Eat Chameleons

817 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航