bzoj 3262: 陌上花开（cdq分治）-白红宇

bzoj 3262: 陌上花开（cdq分治）

阅读量：2143 次

发布时间：2019-04-30

本文共 765 字，大约阅读时间需要 2 分钟。

Time Limit: 20 Sec

Memory Limit: 256 MB

Submit: 2433

Solved: 1087

[ ][ ][ ]

Description

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(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的每级花的数量。

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

模板题，cdq分治可以看

不过有两个地方不一样

①若干朵完全一样的花当成一朵再分治，因为属性一样算做互相超过

③若是x排序，y树状数组，z用cdq分治，一定要先将z离散化，因为它不是1-n的全排列

#include
   
    #include
    
     using namespace std;int k, tre[200005];typedef struct Res{	int x, y, z, ans, sum;	bool operator < (const Res &b) const	{		if(x

转载地址：http://aimgf.baihongyu.com/

你可能感兴趣的文章