BZOJ3262 陌上花开 < CDQ分治 >

Posted on Symbols count in article: 755 Reading time ≈ 3 mins.

Problem

陌上花开

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

有nn朵花，每朵花有三个属性：花形(ss)、颜色(cc)、气味(mm)，用三个整数表示。
现在要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花aa比另一朵花bb要美丽，当且仅sa≥sb,ca≥cb,ma≥mbs_a\ge s_b,c_a\ge c_b,m_a\ge m_b。
显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K  (1≤N≤105,1≤K≤2×105)N,K\;(1\le N\le10^5,1\le K\le2\times10^5)，分别表示花的数量和最大属性值。
以下NN行，每行三个整数si,ci,mi  (1≤si,ci,mi≤K)s_i,c_i,m_i\;(1\le s_i,c_i,m_i\le K)，表示第ii朵花的属性。

Output

包含NN行，分别表示评级为0∼N−10\sim N-1的每级花的数量。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
7
8
9
10
3
1
3
0
1
0
1
0
0
1

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

Solution

三维偏序，CDQ\mathrm{CDQ}分治裸题。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}