【题解】BZOJ4548 小奇的糖果(树状数组)

说在前面：我有个同学叫小奇，他有一个朋友叫达达，达达特爱地理和旅游，初中经常AK地理，好怀恋和他已经达达一起到当时初中附近许多楼盘的顶楼逛的时光...

主要是今天大家讲题的时候我偷偷溜出来到了科技楼七楼，从窗户爬到阳台上，发现顶楼居然有：

天文望远镜一台
气象观测室一间
化学实验室一间
水文实验室一间
Corridors一个
奇怪的植物若干
没有监控

考虑到要求至少没有一种颜色，那么就钦定某种颜色不存在即可

考虑这样一种做法，将所有点按照y从小往大排序，枚举到\(u=(x,y,z)\)时，查询y比他小的\(z\)颜色的点的位置，定位到在\(u\)两侧的点然后查询在\(u\)以下的点的个数，此时由于一定没有\(z\)颜色，所以是合法的。

然后那些一条线往上的方案，可以把y*=-1解决

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<set>

#define DEBUG(s) cerr<<(#s)<<" = "<<(s)<<endl

#define getchar() (__c==__ed?(__ed=__buf+fread(__c=__buf,1,1<<18,stdin),*__c++):*__c++)

using namespace std;  typedef long long ll;   char __buf[1<<18],*__c=__buf,*__ed=__buf;

inline int qr(){

	register int ret=0,f=0;

	register char c=getchar();

	while(!isdigit(c))f|=c==45,c=getchar();

	while(isdigit(c)) ret=ret*10+c-48,c=getchar();

	return f?-ret:ret;

}

const int maxn=1e5+7;

const int inf=1<<30;

struct NODE{

	int x,y,z;

	inline bool operator <(const NODE&A)const{return y<A.y;}

}data[maxn];

int n,k,len;

int sav[maxn];

set<int> s[maxn];

int seg[maxn];

inline void add(const int&pos,const int&tag){

	for(int t=pos;t<=len;t+=t&-t) seg[t]+=tag;

}

inline int que(const int&pos){

	int ret=0;

	for(int t=pos;t>0;t-=t&-t) ret+=seg[t];

	return ret;

}

int work(const int&_f){

	int ret=0;

	for(int t=1;t<=n&&_f;++t) data[t].x=qr(),data[t].y=qr(),data[t].z=qr();

	memset(seg,0,sizeof seg);

	for(int t=1;t<=n;++t) sav[t]=data[t].x;

	sav[n+1]=inf; sav[n+2]=-inf;

	sort(sav+1,sav+n+2+1);

	len=unique(sav+1,sav+n+2+1)-sav-1;

	for(int t=1;t<=n;++t) data[t].x=lower_bound(sav+1,sav+len+1,data[t].x)-sav;

	sort(data+1,data+n+1);

	for(int t=1;t<=k;++t) s[t].clear(),s[t].insert(1),s[t].insert(len);

	for(int t=1;t<=n;++t){

		if(s[data[t].z].find(data[t].x)==s[data[t].z].end()){

			ret=max(ret,que(*s[data[t].z].upper_bound(data[t].x)-1)-que(*--s[data[t].z].upper_bound(data[t].x)));

			s[data[t].z].insert(data[t].x);

		}

		add(data[t].x,1);

	}

	for(int t=1;t<=k;++t){

		int last=1;

		for(set<int>::iterator i=s[t].upper_bound(1);i!=s[t].end();++i)

			ret=max(ret,que(*i-1)-que(last)),last=*i;

	}

	if(_f){

		for(int t=1;t<=n;++t) data[t].y=-data[t].y;

		ret=max(ret,work(0));

	}

	return ret;

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("cpp.in","r",stdin);

	freopen("cpp.out","w",stdout);

#endif

	int T=qr();

	while(T--) n=qr(),k=qr(),printf("%d\n",work(1));

	return 0;

}

巴特西

【题解】BZOJ4548 小奇的糖果(树状数组)

【题解】BZOJ4548 小奇的糖果(树状数组)

最新文章

热门文章