#P3658. Jabberwocky

    ID: 2853 传统题 2000ms 512MiB 尝试: 378 已通过: 109 难度: 7 上传者: 标签>难度分类提高动态规划有限候选集缩减计算几何扫描线排序与序列处理离散化数据结构有序集合树状数组模拟与实现技巧同时事件分阶段处理CF2200

Jabberwocky

题目描述

平面上有 nn 个点,每个点的颜色是 kk 种颜色之一。你可以画一条水平线段,并选择收集其上方或下方一侧的所有点。一个点只有在横坐标落在线段两端之间,并位于所选一侧时,才会被收集。投影恰落在线段端点,或点恰在线段上的情形也计入。下图展示了选择下方一侧的情形。

水平线段与收集区域

求至多能收集多少个点,使收集到的点中至少缺少一种颜色。

输入格式

第一行一个整数 TT,表示测试数据组数。

每组数据第一行两个整数 n,kn,k,分别表示点数和颜色数。接下来 nn 行,每行三个整数 x,y,zx,y,z,表示点的坐标 (x,y)(x,y) 和颜色 zz。

输出格式

每组数据输出一行一个整数,表示最多可收集的点数。

样例

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

数据范围

1≤T≤31\le T\le 3,n,k≤105n,k\le 10^5,∣x∣,∣y∣≤232−1|x|,|y|\le 2^{32}-1,1≤z≤k1\le z\le k。