Atcoder ABC 309 F

题意

n个盒子，长宽高为\(x,y,z,\)(长宽高是相对的，可以任意调换),问是否有一个盒子可以完全容纳另一个盒子，即存在一个\(A_i={x_i,y_i,z_i},A_j={x_j,y_j,z_j}\) ,使得\(x_i<x_j,y_i<y_j,z_i<z_j\)

思路

思考一个简单的问题：对于二元组\((x,y)\)，我们怎么确定存在两个二元组\(x_i<x_j,y_i<y_j\)，答案自然是树状数组，以第一关键字\(x\)为下标，用树状数组维护第一关键字在\([0,x]\)的最小的\(y\)值.
这题就是多了一个关键字而已，以多出的一个关键字排序，之后放在外层枚举，注意外层关键字不能相同。

代码

struct node
{
	int a,b,c;
	//因为可以任意调换，就按从小到大排序
	void init() 
	{
		if(a>b) swap(a,b);
		if(b>c) swap(b,c);
		if(a>b) swap(a,b);
	}
}d[N];

bool cmp(node a,node b) 
{
	return a.a<b.a;
}

int p[N],f[N*3];

int get(int x) 
{
	int ans=inf;
	while(x) ans=min(ans,f[x]),x-=(x&-x);
	return ans;
}

void modify(int x,int y) 
{
	while(x<=n) f[x]=min(f[x],y),x+=(x&-x);
}

void  solve()
{
	cin>>n;
	for(int i=0;i<=n*2;i++) f[i]=inf;//树状数组维护最小值，要
	for(int i=1;i<=n;i++) cin>>d[i].a>>d[i].b>>d[i].c,d[i].init();
	sort(d+1,d+1+n,cmp);//以第一关键字排序
	
	//第二关键字 离散化
	for(int i=1;i<=n;i++) p[i]=d[i].b;
	sort(p+1,p+1+n);
 	for(int i=1;i<=n;i++) 
 	{
 		d[i].b = lower_bound(p+1,p+1+n,d[i].b)-p;
 	}

 	for(int i=1;i<=n;i++)  
 	{
 		if(d[i].a!=d[i+1].a)
 		{	
	 	//已经保证第一关键字一定大于前面的，当前的还未加入树状数组
 			for(int j=i;j>=1;j--) 
 			{
 				if(d[j].a!=d[i].a) break;
 				if(get(d[j].b-1)<d[j].c)
 				{
 					cout<<"Yes\n";
 					return;
 				}
 			}
 			for(int j=i;j>=1;j--) 
 			{
 				if(d[j].a!=d[i].a) break;
 				modify(d[j].b,d[j].c);
 			}
 		}
 	}
 	cout<<"No\n";
}