NekoMio's Blog

美しいものが起こることを常に信じている

题目描述

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

输入格式

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000), 分别表示花的数量和最大属性值。
以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性

输出格式

包含N行,分别表示评级为0…N-1的每级花的数量。

样例输入

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

样例输出

3
1
3
0
1
0
1
0
0
1

提示

1 <= N <= 100,000, 1 <= K <= 200,000

题解

三维偏序
将一个维度作为时间。

比如我令 颜色(c) 为时间维。

那么第一步将除时间(颜色)以外的一个维度排序,
比如说我这里将 花形(s) 排序

那么我们要保证这一维(花形) 时刻有序。

然后我们分治时间(颜色);

我选择的方法是暴力sort, 先递归。

那么在分治后左边的花型一定是小于右边的。

所以只要将左右分别按时间排序, 对于每一个右边的值, 将左边时间比他小的更新到树状数组中。 然后查询第三维小于他的个数就可以更新答案了。

一些具体的细节可以看代码实现

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100005;
const int M = 200005;
struct data
{
int s, c, m, pos, num, ans;
bool operator < (const data &a) const
{
if (s == a.s && c == a.c) return m < a.m;
if (s == a.s) return c < a.c;
return s < a.s;
}
}a[N], b[N];
const bool cmp(const data &a, const data &b)
{
if (a.c == b.c) a.m < b.m;
return a.c < b.c;
}
int Sum[M], cnt, Color[M], C;
#define lowbit(_) ((_) & (-_))
void add(int x, int c)
{
for (int i = x; i <= M; i += lowbit(i))
{
if (Color[i] != C) Sum[i] = 0;
Color[i] = C;
Sum[i] += c;
}
}
int Query(int x)
{
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i))
{
if (Color[i] == C)
ans += Sum[i];
}
return ans;
}
void CDQ(int l, int r)
{
if (l == r) return;
int mid = l + r >> 1;
CDQ(l, mid), CDQ(mid + 1, r);
sort(b + l, b + mid + 1, cmp);
sort(b + mid + 1, b + r + 1, cmp);
C++;
for (int j = mid + 1, i = l; j <= r; j++)
{
for (; b[i].c <= b[j].c && i <= mid; i++)
add(b[i].m, b[i].num);
b[j].ans += Query(b[j].m);
}
}
int main()
{
int n, k;
scanf ("%d%d", &n, &k);
for (int i = 1; i <= n; i++){
scanf ("%d%d%d", &a[i].s, &a[i].c, &a[i].m);
a[i].pos = i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)
{
if (a[i].c == a[i - 1].c && a[i].s == a[i - 1].s && a[i].m == a[i - 1].m)
b[cnt].num++;
else
b[++cnt] = a[i], b[cnt].num = 1;
}
// for (int i = 1; i <= cnt; i++) printf ("%d%c", b[i].pos, " \n"[i == cnt]);
CDQ(1, cnt);
// for (int i = 1; i <= cnt; i++) printf ("%d%c", b[i].ans, " \n"[i == cnt]);
// while(1);
static int Ans[N];
for (int i = 1; i <= cnt; i++) Ans[b[i].ans + b[i].num - 1] += b[i].num;
for (int i = 0; i < n; i++) printf ("%d\n", Ans[i]);
// while (1);
}

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2017/10/25/116/

本文最后更新于 天前,文中所描述的信息可能已发生改变