#P4062. [Cerc2012]Jewel heist

    ID: 3265 传统题 2000ms 128MiB 尝试: 198 已通过: 56 难度: 7 上传者: 标签>CF2200提高扫描线树状数组有序集合离散化同时事件分阶段处理添加哨兵鸣谢Tjz

[Cerc2012]Jewel heist

题目描述

擅长偷盗的卢平想要偷走邪恶的欧文收藏的珠宝。

欧文在他的商店里放置了 nn 个珠宝。 每个珍贵的石头一定有着 kk 种颜色之一的颜色。

展览馆非常的大,我们可以将珠宝视为欧几里得平面上的一些互异的点。

这场展览由一些非常珍贵的报警设备来保护。

卢平发明了一种装置:一个巨大的机械臂,可以用来抢欧文的珠宝而不被任何报警设备发现。

这只机械臂可以做一次抢的操作(也仅有一次)可以将在某条水平线段及其下方的所有珠宝拿走(如图)。

卢平很容易偷走所有的珠宝,但是他知道,他拿得越多就越难不被发现。他决定选择一种安全的方案,他拿走的珠宝的颜色数不会超过 kk。

请你计算他在不拿走所有颜色的情况下最多拿多少个珠宝。

输入格式

第一行一个正整数 TT,表示有 TT 组数据。

每组数据第一行两个正整数 nn 和 kk,表示珠宝数量和颜色数量。

接下来 nn 行,每行三个整数 xj,yj,cjx_j, y_j, c_j,表示第 jj 个珠宝在(xj,yjx_j, y_j)的位置,颜色为 cjc_j。

你可以认为每种颜色至少有一个珠宝。

输出格式

对于每组数据输出一行,即最大的可能偷走的珠宝数量。

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

数据规模与约定

对于 100%100\% 的数据满足,2≤n≤2×1052 \le n \le 2\times 10^5,2≤k≤n2 \le k \le n,1≤xj,yj≤1091 \le x_j, y_j \le 10^9,1≤cj≤k1 \le c_j \le k。