BZOJ3262 陌上花开 < CDQ分治 >

Problem

陌上花开

Description

有朵花，每朵花有三个属性：花形()、颜色()、气味()，用三个整数表示。
现在要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花比另一朵花要美丽，当且仅。
显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为，分别表示花的数量和最大属性值。
以下行，每行三个整数，表示第朵花的属性。

Output

包含行，分别表示评级为的每级花的数量。

Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Sample Output

3
1
3
0
1
0
1
0
0
1

标签：CDQ分治 树状数组 三维偏序

Solution

三维偏序，分治裸题。

首先对排序，记录每朵花排名。分治计算，对于区间，先按值排序，再考虑该区间中的花对中的花产生的贡献，即若排名小于等于，将其值加入树状数组；否则统计中值比它小的花对它的贡献，即为树状数组中的前缀和。
注意若有相同的一段花，则其答案一定是排在最后的这种花的答案。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 200000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, tr[MAX_M+5], cnt[MAX_N+5];
struct node {int x, y, z, p, s;} a[MAX_N+5], b[MAX_N+5];
void inc(int p) {for (; p <= m; p += (p&-p)) tr[p]++;}
void dec(int p) {for (; p <= m; p += (p&-p)) tr[p]--;}
int sum(int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[p]; return ret;}
bool cmp(const node &a, const node &b)
	{return a.x == b.x ? (a.y == b.y ? (a.z < b.z) : a.y < b.y) : a.x < b.x;}
bool operator == (node a, node b) {return a.x == b.x && a.y == b.y && a.z == b.z;}
void CDQ(int s, int t) {
    if (s == t) return; CDQ(s, mid), CDQ(mid+1, t);
    for (int i = s, p1 = s, p2 = mid+1; i <= t; i++)
        b[i] = (p1 <= mid && (p2 > t || a[p1].y <= a[p2].y)) ? a[p1++] : a[p2++];
    for (int i = s; i <= t; i++) a[i] = b[i];
    for (int i = s; i <= t; i++)
        if (a[i].p <= mid) inc(a[i].z);
        else a[i].s += sum(a[i].z);
    for (int i = s; i <= t; i++)
        if (a[i].p <= mid) dec(a[i].z);
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        read(a[i].x), read(a[i].y), read(a[i].z);
    sort(a+1, a+n+1, cmp);
    for (int i = n-1; i >= 1; i--)
        if (a[i] == a[i+1]) a[i].s = a[i+1].s+1;
    for (int i = 1; i <= n; i++) a[i].p = i;
    CDQ(1, n); for (int i = 1; i <= n; i++) cnt[a[i].s]++;
    for (int i = 0; i < n; i++) printf("%d\n", cnt[i]);
    return 0;
}