Farmer John has N (1 <= N <= 25,000) rectangular barns on his farm, all with sides parallel to the X and Y axes and integer corner coordinates in the range 0..1,000,000. These barns do not overlap although they may share corners and/or sides with other barns. Since he has extra cows to milk this year, FJ would like to expand some of his barns. A barn has room to expand if it does not share a corner or a wall with any other barn. That is, FJ can expand a barn if all four of its walls can be pushed outward by at least some amount without bumping into another barn. If two barns meet at a corner, neither barn can expand. Please determine how many barns have room to expand.

* Line 1: A single integer, N

* Lines 2..N+1: Four space-separated integers A, B, C, and D, describing one barn. The lower-left corner of the barn is at (A,B) and the upper right corner is at (C,D).

* Line 1: A single integer that is the number of barns that can be expanded.

 输出可扩张的牛棚数．

Gold

  1 #include<set>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #define Rep(i,x,y) for(int i=x;i<y;++i)
  7 #define For(i,x,y) for(int i=x;i<=y;++i)
  8 using namespace std;
  9 const int N = 3e5+5;
 10 const int M = 1e6+5;
 11 struct data{
 12     int x,u,d,id;
 13     bool kd;
 14     bool operator < (const data&b) const{
 15         return x<b.x||x==b.x&&kd<b.kd;
 16     }
 17 }a[N];
 18 struct bit{
 19     int c[M];
 20     #define lowbit(x) (x&-x)
 21     void insert(int x){
 22         for(int i=x;i<M;i+=lowbit(i))
 23             c[i]++;
 24     }
 25     void erase(int x){
 26         for(int i=x;i<M;i+=lowbit(i))
 27             c[i]--;    
 28     }
 29     int query(int x){
 30         if(!x) return 0;
 31         int res=0;
 32         for(int i=x;i;i-=lowbit(i))
 33             res+=c[i];
 34         return res;
 35     }
 36     void init(){
 37         memset(c,0,sizeof(c));
 38     }
 39 }T1,T2;
 40 int cnt;
 41 int n;
 42 bool nok[N];
 43 int f[M][2];
 44 void del(int i){
 45     T1.erase(a[i].d);
 46     T2.erase(a[i].u+1);
 47     f[a[i].u][0]=0;
 48     f[a[i].d][1]=0;
 49 }
 50 void INS(int i){
 51     f[a[i].u][0]=a[i].id;
 52     f[a[i].d][1]=a[i].id;
 53     T1.insert(a[i].d);
 54     T2.insert(a[i].u+1);
 55 }
 56 void ins(int l,int r){
 57     For(i,l,r)
 58         INS(i);
 59     For(i,l,r){
 60         del(i);
 61         if(f[a[i].u][1]){
 62             nok[a[i].id]=1;
 63             nok[f[a[i].u][1]]=1;
 64         }
 65         if(f[a[i].d][0]){
 66             nok[a[i].id]=1;
 67             nok[f[a[i].d][0]]=1;
 68         }
 69         if(T1.query(a[i].u)-T2.query(a[i].d)>0) nok[a[i].id]=1;
 70         INS(i);
 71     }
 72 }
 73 int main(){
 74     scanf("%d",&n);
 75     For(i,1,n){
 76         int l,r,u,d;
 77         scanf("%d%d%d%d",&l,&d,&r,&u);
 78         ++l;++r;++d;++u;
 79         a[++cnt]=(data){l,u,d,i,0};
 80         a[++cnt]=(data){r,u,d,i,1};
 81     }
 82     n<<=1;
 83     sort(a+1,a+n+1);
 84     for(int i=1;i<=n;){
 85         int l=i;int r=i;
 86         for(;r<=n&&a[r].x==a[l].x&&a[r].kd==0;++r);
 87         ins(l,r-1);
 88         for(;r<=n&&a[r].kd==1;++r) 
 89             del(r);
 90         i=r;
 91     }
 92     memset(f,0,sizeof(f));
 93     T1.init();
 94     T2.init();
 95     for(int i=n;i;){
 96         int r=i;int l=i;
 97         for(;l>0&&a[l].x==a[r].x&&a[l].kd==1;--l);
 98         ins(l+1,r);
 99         for(;l>0&&a[l].kd==0;--l) del(l);
100         i=l;
101     }
102     int res=0;
103     For(i,1,n/2) if(!nok[i]) ++res;
104     cout<<res<<endl;
105     return 0;
106 }