题解：P3079 [USACO13MAR] Farm Painting S

· · 题解

P3079 [USACO13MAR] Farm Painting S

Description

给出 n 个矩形，统计有多少矩形不被任何其他矩形包含。

Solution

一个矩形 (xl,xr,yl,yr) 被 (xL,xR,yL,yR) 包含，当且仅当 xL \le xl \land xr \le xR \land yL \le yl \land yr \le yR。

因此，需要对于每一个矩形，判断是否存在不同的矩形，满足 xL \le xl \land xr \le xR \land yL \le yl \land yr \le yR。

有四维的偏序关系，但是因为只需要判存在，转化为是否满足 \max_{xL \le xl \land xr \le xR \land yL \le yl }yR \ge yr 即可。

跑一遍三维偏序就行，记得判重复。

时间 O(n \log^2 n)，空间 O(n)，随便过。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
const int N=5e4+5;
int n;
int cnt;
int val[N],tot;
int maxyr[N],YR[N];
struct sqr{
  int xl,xr,yl,yr,id;
  bool operator == (const sqr &s) const{return xl==s.xl&xr==s.xr&yl==s.yl&yr==s.yr;}
}a[N],b[N];
bool cmpyr(const sqr &x,const sqr &y){return x.yr>y.yr;}
bool cmpyl(const sqr &x,const sqr &y){return x.yl==y.yl?cmpyr(x,y):x.yl<y.yl;}
bool cmpxr(const sqr &x,const sqr &y){return x.xr==y.xr?cmpyl(x,y):x.xr>y.xr;}
bool cmpxl(const sqr &x,const sqr &y){return x.xl==y.xl?cmpxr(x,y):x.xl<y.xl;}
int t[N];
void upd(int p,int x){
  while(p<=tot) t[p]=max(t[p],x),p+=p&-p;
}
void clr(int p){
  while(p<=tot) t[p]=0,p+=p&-p;
}
int qry(int p){
  int res=0;
  while(p) res=max(res,t[p]),p&=p-1;
  return res;
}
void cdq(int l,int r){
  if(l==r) return;
  int mid=(l+r)>>1;
  cdq(l,mid);
  cdq(mid+1,r);
  int j=l;
  rep(i,mid+1,r){
    while(j<=mid&&cmpxr(a[j],a[i])) upd(a[j].yl,a[j].yr),++j;
    maxyr[a[i].id]=max(maxyr[a[i].id],qry(a[i].yl));
  }
  rep(i,l,j-1) clr(a[i].yl);
  int p=j=l;
  rep(i,mid+1,r){
    while(j<=mid&&cmpxr(a[j],a[i])) b[p++]=a[j++];
    b[p++]=a[i];
  }
  while(j<=mid) b[p++]=a[j++];
  rep(i,l,r) a[i]=b[i];
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  rep(i,1,n){
    int xl,xr,yl,yr;
    cin>>xl>>yl>>xr>>yr;
    a[i]={xl,xr,yl,yr,i};
    val[++tot]=yl;
    YR[i]=yr;
  }
  sort(val+1,val+tot+1);
  tot=unique(val+1,val+tot+1)-val-1;
  rep(i,1,n) a[i].yl=lower_bound(val+1,val+tot+1,a[i].yl)-val;
  sort(a+1,a+n+1,cmpxl);
  rep(i,1,n){
    if(a[i]==a[i-1]) maxyr[a[i].id]=maxyr[a[i-1].id]=1000000;
    else b[++cnt]=a[i];
  }
  rep(i,1,cnt) a[i]=b[i];
  cdq(1,cnt);
  int ans=0;
  rep(i,1,n) if(maxyr[i]<YR[i]) ++ans;
  cout<<ans<<'\n';
  return 0;
}

最大点 40 ms。