【BZOJ4548】小奇的糖果

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

Sample Output

题解：一开始想的是：不包含所有颜色=有一种颜色不出现，所以我们枚举不出现哪个颜色即可。而一个颜色出现的位置有很多，我们相当于用这些点将平面分成若干个部分，然后在每个部分里都统计一下点的个数即可。不过该怎么分呢？蒟蒻就卡到这了，然而看大爷的博客发现可以分治。。。感觉神的不行。

所以还是来看一种简单的方法吧！我们先只考虑向下的情况。我们将所有点按y值从小到大排序，然后从下往上一层一层的加入到平面中（一层一层指的是y值相同的点要同时加入）。在加入一个点之前，我们先用set找到与它颜色相同的，已经加入到平面中的点的，x值的前驱和后继，然后用树状数组统计一下前驱到后继之间这部分的点数，然后再将这个点加进去。最后可能有没被统计过得部分，再查询一遍所有点即可。

向上的情况呢？反过来做一遍即可。

PS：如果你将一个一个加点改成一个一个删点，那就可以用链表来维护前驱后继了~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <set>

#include <utility>

#define mp(A,B) make_pair(A,B)

using namespace std;

const int maxn=100010;

typedef pair<int,int> pii;

int n,m,nm,cnt,ans;

struct point

{

	int x,y,col;

}p[maxn];

struct node

{

	int val,org;

}num[maxn];

int v[maxn],vis[maxn],s[maxn],st[maxn];

set<int> S[maxn];

set<int>::iterator it;

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

bool cmpv(const node &a,const node &b)

{

	return a.val<b.val;

}

bool cmpy(const point &a,const point &b)

{

	return a.y<b.y;

}

inline void updata(int x)

{

	for(int i=x;i<=nm;i+=i&-i)	s[i]++;

}

inline int query(int x)

{

	int i,ret=0;

	for(i=x;i;i-=i&-i)	ret+=s[i];

	return ret;

}

inline void insert(int x)

{

	S[p[x].col].insert(p[x].x),updata(p[x].x),cnt+=(!vis[p[x].col]),vis[p[x].col]=1;

}

inline void calc(int x)

{

	int a,b;

	it=S[p[x].col].lower_bound(p[x].x),b=(it==S[p[x].col].end()?nm+1:(*it));

	it=S[p[x].col].upper_bound(p[x].x),a=(it==S[p[x].col].begin()?0:(*(--it)));

	ans=max(ans,query(b-1)-query(a));

}

inline void init()

{

	memset(vis,0,sizeof(vis)),memset(s,0,sizeof(s)),cnt=0;

	for(int i=1;i<=m;i++)	S[i].clear();

}

void work()

{

	n=rd(),m=rd(),nm=ans=0;

	int i,j,a,b;

	for(i=1;i<=n;i++)	num[i].val=rd(),num[i].org=i,p[i].y=rd(),p[i].col=rd();

	sort(num+1,num+n+1,cmpv);

	for(i=1;i<=n;i++)

	{

		if(i==1||num[i].val>num[i-1].val)	nm++;

		p[num[i].org].x=nm;

	}

	p[0].x=1,p[n+1].x=n;

	sort(p+1,p+n+1,cmpy);

	init();

	for(i=1;i<=n;i++)

	{

		st[st[0]=1]=i;

		while(i<n&&p[i+1].y==p[i].y)	st[++st[0]]=++i;

		for(j=1;j<=st[0];j++)	calc(st[j]);

		for(j=1;j<=st[0];j++)	insert(st[j]);

		if(cnt<m)	ans=max(ans,i);

	}

	for(i=1;i<=n;i++)

	{

		it=S[p[i].col].upper_bound(p[i].x),b=(it==S[p[i].col].end()?nm+1:(*it));

		it=S[p[i].col].lower_bound(p[i].x),a=(it==S[p[i].col].begin()?0:(*(--it)));

		ans=max(ans,query(b-1)-query(p[i].x)),ans=max(ans,query(p[i].x-1)-query(a));

	}

	init();

	for(i=n;i;i--)

	{

		st[st[0]=1]=i;

		while(i>1&&p[i-1].y==p[i].y)	st[++st[0]]=--i;

		for(j=1;j<=st[0];j++)	calc(st[j]);

		for(j=1;j<=st[0];j++)	insert(st[j]);

		if(cnt<m)	ans=max(ans,n-i+1);

	}

	for(i=1;i<=n;i++)

	{

		it=S[p[i].col].upper_bound(p[i].x),b=(it==S[p[i].col].end()?nm+1:(*it));

		it=S[p[i].col].lower_bound(p[i].x),a=(it==S[p[i].col].begin()?0:(*(--it)));

		ans=max(ans,query(b-1)-query(p[i].x)),ans=max(ans,query(p[i].x-1)-query(a));

	}

	printf("%d\n",ans);

}

int main()

{

	int T=rd();

	while(T--)	work();

	return 0;

}