Description
有 N 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾
起多少糖果,使得获得的糖果并不包含所有的颜色。
Input
包含多组测试数据,第一行输入一个正整数 T 表示测试数据组数。
接下来 T 组测试数据,对于每组测试数据,第一行输入两个正整数 N、K,分别表示点数和颜色数。
接下来 N 行,每行描述一个点,前两个数 x, y (|x|, |y| ≤ 2^30 - 1) 描述点的位置,最后一个数 z (1 ≤ z ≤
k) 描述点的颜色。
对于 100% 的数据,N ≤ 100000,K ≤ 100000,T ≤ 3
Output
对于每组数据在一行内输出一个非负整数 ans,表示答案
Sample Input
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
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
Sample Output
5
HINT
Source
By Hzwer
树状数组+链表~
注意xr[i]要先设置为n+1!
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int t,n,k,ans,x[100002],y[100001],len1,len2,c[100002],fi[100002],xl[100002],xr[100002];struct node{int x,y,col,id;
}a[100001];bool operator < (node u,node v)
{return u.x<v.x;
}bool cmp(node u,node v)
{return u.y<v.y;
}int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int v)
{for(;u<=n+1;u+=u&(-u)) c[u]+=v;
}int cal(int u)
{int now=0;for(;u;u-=u&(-u)) now+=c[u];return now;
}void update(int l,int r)
{if(l>r) return;ans=max(ans,cal(r)-cal(l-1));
}void solve()
{x[0]=0;x[n+1]=n+1;memset(c,0,sizeof(c));memset(fi,0,sizeof(fi));sort(a+1,a+n+1);for(int i=1;i<=n;i++) add(a[i].x,1);for(int i=1;i<=n;i++){int t=a[i].id,l=fi[a[i].col];xl[t]=l;xr[t]=n+1;if(l) xr[l]=t;update(x[l]+1,x[t]-1);fi[a[i].col]=t;}for(int i=1;i<=k;i++) update(x[fi[i]]+1,n+1);sort(a+1,a+n+1,cmp);for(int i=1,j=1;i<=n;i++){while(j<=n && a[i].y==a[j].y) add(a[j].x,-1),j++;xl[xr[a[i].id]]=xl[a[i].id];xr[xl[a[i].id]]=xr[a[i].id];update(x[xl[a[i].id]]+1,x[xr[a[i].id]]-1);}
}int main()
{t=read();while(t--){n=read();k=read();ans=0;for(int i=1;i<=n;i++) x[i]=a[i].x=read(),y[i]=a[i].y=read(),a[i].col=read(),a[i].id=i;sort(x+1,x+n+1);sort(y+1,y+n+1);len1=unique(x+1,x+n+1)-x-1;len2=unique(y+1,y+n+1)-y-1;for(int i=1;i<=n;i++){a[i].x=lower_bound(x+1,x+len1+1,a[i].x)-x;a[i].y=lower_bound(y+1,y+len2+1,a[i].y)-y;}for(int i=1;i<=n;i++) x[i]=a[i].x;solve();for(int i=1;i<=n;i++) a[i].y*=-1;solve();printf("%d\n",ans);}return 0;
}