#P4548. 小奇的糖果

    ID: 3669 传统题 1000ms 256MiB 尝试: 704 已通过: 212 难度: 7 上传者: 标签>CF2200提高+/省选-扫描线树状数组有序集合离散化同时事件分阶段处理添加哨兵ByHzwer

小奇的糖果

题目描述

有 nn 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。

求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。

输入格式

包含多组测试数据,第一行输入一个正整数 TT,表示测试数据组数。

接下来 TT 组测试数据,对于每组测试数据,第一行输入两个正整数 n,kn,k 分别表示点数和颜色数。

接下来 nn 行,每行描述一个点,前两个数 x,yx,y 描述点的位置,最后一个数 zz 描述点的颜色。

输出格式

对于每组数据在一行内输出一个非负整数 ansans,表示答案。

样例输入

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\% 的数据,1≤n,k≤1051\le n,k \le 10^5,1≤T≤31 \le T \le 3,∣x∣,∣y∣≤230−1|x|,|y| \le 2^{30} - 1,1≤z≤k1 \le z \le k。

题目来源

By Hzwer