F - Box in Box
首先,每个长方体的\(h,w,d\)都是可以任意互换的,所以我们考虑用\(a_0,a_1,a_2\)来代替它们(\(a_0\leq a_1\leq a_2\))
然后可以发现一个规律,我们肯定是用\(a_0\)和\(a_0\)比较,\(a_1\)和\(a_1\)比较,\(a_2\)和\(a_2\)比较
那么现在显然就是三位偏序,可以上\(CDQ\)了,先对\(a_0\)进行排序,但是因为题目要求的是严格大于,所以在\(CDQ\)时,\(mid\)不一定是取\(\frac{l+r}2\),而是一个使得\(mid\)的\(a_0\)和\(mid+1\)的\(a_0\)不相同的,尽量靠近中间的位置
因为若当前区间的\(l\)的\(a_0\)和\(r\)的\(a_0\)都相等了,我们就不用管这个区间了,所以即使我们并没有在下标上进行二分,但是我们相当于在\(a_0\)的值域上进行了二分(并不是严格二分,只是一个相当于在二分的过程),所以复杂度没有问题
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,lsh[N],tot;
struct node{
int a[3];
bool operator < (const node &other)const{
return a[0]<other.a[0];
}
}cn[N];
bool cmp(node a,node b){
return a.a[1]<b.a[1];
}
map<int,int> st,ed;
int c[N];
void add(int x,int y){
for(;x<=tot;x+=x&-x) c[x]+=y;
}
int ask(int x){
int ans=0;
for(;x;x-=x&-x) ans+=c[x];
return ans;
}
void solve(int l,int r){
if(cn[l].a[0]==cn[r].a[0]) return;
int mid=l+r>>1;
if(cn[mid].a[0]==cn[mid+1].a[0]){
int len1=st[cn[mid].a[0]]-l,len2=r-ed[cn[mid].a[0]];
if(len1<len2) mid=ed[cn[mid].a[0]];
else mid=st[cn[mid].a[0]]-1;
}
solve(l,mid),solve(mid+1,r);
sort(cn+l,cn+mid+1,cmp),sort(cn+mid+1,cn+r+1,cmp);
int a=l,b=mid+1;
for(;b<=r;++b){
while(a<=mid&&cn[a].a[1]<cn[b].a[1]) add(cn[a].a[2],1),++a;
if(ask(cn[b].a[2]-1)){ puts("Yes"); exit(0); }
}
for(int i=l;i<a;++i) add(cn[i].a[2],-1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d%d",&cn[i].a[0],&cn[i].a[1],&cn[i].a[2]),sort(cn[i].a,cn[i].a+3),lsh[++tot]=cn[i].a[2];
sort(cn+1,cn+n+1),sort(lsh+1,lsh+tot+1),tot=unique(lsh+1,lsh+tot+1)-lsh-1;
for(int i=1;i<=n;++i){
if(!st[cn[i].a[0]]) st[cn[i].a[0]]=i;
ed[cn[i].a[0]]=i;
cn[i].a[2]=lower_bound(lsh+1,lsh+tot+1,cn[i].a[2])-lsh;
}
solve(1,n);
puts("No");
return 0;
}
标签:Box,二分,abc309,cn,int,mid,const
From: https://www.cnblogs.com/LuoyuSitfitw/p/17558454.html