原题：EAST! 模拟赛 Round XV 呓语

「题目背景」

小奇不小心让糖果散落到了地上，它对着满地的彩色糖果胡思乱想。

「问题描述」

有 N 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。

「输入格式」

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

接下来 T 组测试数据,对于每组测试数据,第一行输入两个正整数 N、K,分别表示点数和颜色数。

接下来 N 行,每行描述一个点,前两个数 x, y (|x|, |y| ≤ 2^30 – 1) 描述点的位置,最后一个数 z (1 ≤ z ≤ k) 描述点的颜色。

「输出格式」

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

「样例输入」

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

「数据范围」

对于 30% 的数据,N ≤ 100;

对于 60% 的数据,N ≤ 5000;

对于 100% 的数据,N ≤ 100000,K ≤ 100000,T ≤ 3。

题解

维护树状数组实现查询横坐标在一段区间内的点的个数。

维护双向链表实现查询一个点左(右)边横坐标最大(小)的与它颜色相同

的点。

 下面只考虑取线段下方的点的情况:

 1.枚举没有取到的颜色,找出所有不包含这种颜色的区间,更新答案。

  2.按照纵坐标从大到小枚举所有的点,分别在树状数组和双向链表中删除当前点,并利用这个点左右两边和它颜色相同的点之间的区间内点的个数更新答案。

 将所有点的纵坐标取相反数,按照上述方式即可求出只取线段上方的点时的答案。

 时间复杂度 O(n*log n)。