bzoj 3262 ：陌上花開 （cdq分治 三維偏序）

題目描述：有n朵花,每朵花有三個屬性:花形(s)、顔色©、氣味(m),用三個整數表示。

現在要對每朵花評級,一朵花的級别是它擁有的美麗能超過的花的數量。

定義一朵花A比另一朵花B要美麗,當且僅Sa>=Sb,Ca>=Cb,Ma>=Mb。

顯然,兩朵花可能有同樣的屬性。需要統計出評出每個等級的花的數量。

Input

第一行為N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的數量和最大屬性值。

以下N行，每行三個整數si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的屬性

Output

包含N行，分别表示評級為0…N-1的每級花的數量。

裸的三維偏向問題，但是花的屬性可能相同，顯然相同的花答案是一樣的，将它們離散化縮點聚在一起即可，最後答案加上這種花的數量。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
#define lowbit(i) (i & (-i))
struct node {
	int s,c,m,id,cnt;
}q[maxn],tmp[maxn];
int sum[maxn],n,k,top;
int ans[maxn];
int vis[maxn];
bool cmp(node a,node b) {
	if(a.s == b.s) {
		if(a.c == b.c) return a.m < b.m;
		return a.c < b.c;
	}
	return a.s < b.s;
}
int cal(node a,node b) {
	if(a.s < b.s) return -1;
	else if(a.s > b.s) return 1;
	else if(a.s == b.s) {
		if(a.c < b.c) return -2;
		else if(a.c > b.c) return 2;
		else if(a.c == b.c) {
			if(a.m < b.m) return -3;
			else if(a.m > b.m) return 3;
			else if(a.m == b.m) return 0;
		}
	}
}
int getsum(int p) {
	int ans = 0;
	for(; p; p -= lowbit(p)) ans += sum[p];
	return ans;
}
void modify(int p,int v) {
	for(; p <= k; p += lowbit(p)) sum[p] += v;
}
void cdq(int l,int r) {
	if(l == r) return;
	int mid = l + r >> 1;
	cdq(l,mid);cdq(mid + 1,r);
	top = 0;
	for(int i = l,j = mid + 1; i <= mid || j <= r;) {
		if(i <= mid && (j > r || q[i].c <= q[j].c)) {
			modify(q[i].m,q[i].cnt);
			tmp[++top] = q[i++];
		}
		else {
			ans[q[j].id] += getsum(q[j].m);
			tmp[++top] = q[j++];
		}
	}
	for(int i = l; i <= mid; i++)
		modify(q[i].m,-q[i].cnt);
	for(int i = l; i <= r; i++) 
		q[i] = tmp[i - l + 1];
}
int main() {
	scanf("%d%d",&n,&k);
	for(int i = 1; i <= n; i++)
		scanf("%d%d%d",&q[i].s,&q[i].c,&q[i].m);
	sort(q + 1,q + n + 1,cmp);
	int tot = 0;
	for(int i = 1; i <= n; i++) {
		if(tot && cal(q[i],q[tot]) == 0) {
			q[tot].cnt++;
		}
		else {
			q[++tot] = q[i];
			q[tot].id = tot;
			q[tot].cnt = 1;
		}
	}
	cdq(1,tot);
	for(int i = 1; i <= tot; i++) {
		ans[q[i].id] += q[i].cnt - 1;
	}
	for(int i = 1;i <= tot; i++) {
		vis[ans[q[i].id]] += q[i].cnt;
	}
	for(int i = 0; i < n; i++) 
		printf("%d\n",vis[i]);	
	return 0;
}