【题解】 BZOJ4548 小奇的糖果

本文同步在学弟ZCDHJ的个人博客发布，审核需要一段时间.

传送门

---

考虑题目中获得的糖果并不包含所有的颜色这句话,发现相当于我们可以直接选取某一个颜色强制不能选(这样子一定最优).

然后就可以考虑分开解决上面和下面.

先考虑下面:

1. 枚举颜色然后搞区间(不能包含这一种颜色)
2. 按照横坐标的顺序删点,然后再看删除的点的颜色的区间是否会被更新

以上操作的话,查询区间可以用双向链表,区间求点(和)可以使用树状数组.

差不多就这样子了.

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<iostream>

using namespace std;

inline int gi(){

	int sum=0,f=1;char ch=getchar();

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

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

int ans,n,K,c[500010],x[500010],l[500010],r[500010],last[500010],b[500010];

struct node{

	int id,x,y,z;

}p[500010];

int lowbit(int x){

	return x&-x;

}

void add(int x,int d){

	for(;x<=n+1;x+=lowbit(x))c[x]+=d;

}

int query(int x){

	int res=0;

	for(;x>0;x-=lowbit(x))res+=c[x];

	return res;

}

bool cmp1(node a,node b){

	return a.x<b.x;

}

bool cmp2(node a,node b){

	return a.y<b.y;

}

void update(int l,int r){

	if(l>r)return;

	ans=max(ans,query(r)-query(l-1));

}

void solve(){

	x[0]=0;x[n+1]=n+1;

	memset(c,0,sizeof(c));memset(last,0,sizeof(last));

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

	for(int i=1;i<=n;i++)add(p[i].x,1);

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

		int t=p[i].id,L=last[p[i].z];

		l[t]=L;r[t]=n+1;

		if(L)r[L]=t;update(x[L]+1,x[t]-1);

		last[p[i].z]=t;

	}

	for(int i=1;i<=K;i++)update(x[last[i]]+1,n+1);

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

	for(int i=1,j=1;i<=n;i++){

		int t=p[i].id;

		while(j<=n && p[i].y==p[j].y)add(p[j].x,-1),j++;

		l[r[t]]=l[t];r[l[t]]=r[t];

		update(x[l[t]]+1,x[r[t]]-1);

	}

}

int main(){

#ifndef ONLINE_JUDGE

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

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

#endif

	int T=gi();

	while(T--){

		ans=0;

		n=gi();K=gi();

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

			p[i].x=gi();p[i].y=gi();p[i].z=gi();

			p[i].id=i;

		}

		for(int i=1;i<=n;i++)b[i]=p[i].x;

		sort(&b[1],&b[n+1]);

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

			p[i].x=lower_bound(b+1,b+n+1,p[i].x)-b;

			x[i]=p[i].x;

		}

		solve();

		for(int i=1;i<=n;i++)p[i].y=-p[i].y;

		solve();

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

	}

	return 0;

}