问题描述
平面上有n个点，每个点有一种颜色。对于某一条线段，选择所有其上方或下方的点。求：在不包含所有颜色的点的前提下，选择的点数最多是多少。（本题中如果存在某颜色没有相应的点，那么选择任何线段都不算做包含所有颜色）
输入格式
包含多组测试数据,第一行输入一个正整数 T 表示测试数据组数。
接下来 T 组测试数据,对于每组测试数据,第一行输入两个正整数 N、K,分别表示点数和颜色数。
接下来 N 行,每行描述一个点,前两个数 x, y (|x|, |y| ≤ 2^30 - 1) 描述点的位置,最后一个数 z (1 ≤ z ≤ k) 描述点的颜色。
对于 100% 的数据,N ≤ 100000,K ≤ 100000,T ≤ 3
输出格式
对于每组数据在一行内输出一个非负整数 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
解析
题目的意思就是求一个不包含某一种颜色的点的区域，也就是求不包含这种颜色的极大子矩形。
不妨先考虑求线段下方的点。那么，对于一个点，它的极大子矩形就是如下图所示的这样一个区域：
其中ABC三点颜色相同，且BC是x坐标最靠近A的点。这样就保证了子矩形中没有与A颜色相同的点。那么怎样求点的数量呢？可以先离散化x坐标，然后用树状数组维护每个x坐标上有几个点即可。另外，要按y坐标从小到大加入树状数组中，保证每次求区间和时都是在线段以下的点。至于求一个点在x轴上最近的两点可以用STL的set实现。
求线段上方的只需要将y坐标取相反数然后进行同样的操作即可。
代码
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#include <cstring>
#define int long long
#define N 100002
using namespace std;
struct node{
int x,y,col;
}a[N];
int t,n,m,i,tmp[N],c[N],ans;
int read()
{
char c=getchar();
int w=0,f=1;
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w*f;
}
int my_comp(const node &a,const node &b)
{
return a.y<b.y;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y;
}
int ask(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i];
return ans;
}
void work()
{
set<int> s[N];
int i=1,j=1;
memset(c,0,sizeof(c));
for(int i=1;i<=m;i++) s[i].insert(0),s[i].insert(n+1);
while(i<=n){
while(a[j].y==a[i].y) j++;
for(int k=i;k<j;k++){
int l=*(--s[a[k].col].upper_bound(a[k].x));
int r=*(s[a[k].col].lower_bound(a[k].x))-1;
ans=max(ans,ask(r)-ask(l));
}
for(int k=i;k<j;k++){
add(a[k].x,1);
s[a[k].col].insert(a[k].x);
}
i=j;
}
for(i=1;i<=m;i++){
set<int>::iterator it1=s[i].begin(),it2;
while(1){
it2=it1;it2++;
if(it2==s[i].end()) break;
ans=max(ans,ask((*it2)-1)-ask(*it1));
it1++;
}
}
}
signed main()
{
t=read();
while(t--){
ans=0;
n=read();m=read();
for(i=1;i<=n;i++){
a[i].x=read(),a[i].y=read(),a[i].col=read();
tmp[i]=a[i].x;
}
sort(tmp+1,tmp+n+1);
int n1=unique(tmp+1,tmp+n+1)-tmp-1;
for(i=1;i<=n;i++) a[i].x=lower_bound(tmp+1,tmp+n1+1,a[i].x)-tmp;
sort(a+1,a+n+1,my_comp);
work();
for(i=1;i<=n;i++) a[i].y=-a[i].y;
sort(a+1,a+n+1,my_comp);
work();
printf("%lld\n",ans);
}
return 0;
}