Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3075 Accepted Submission(s): 1616
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cstring> #include <map> #include <queue> using namespace std; typedef pair<int,int> pii ; typedef long long LL; #define X first #define Y second #define root 1,n,1 #define lr rt<<1 #define rr rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const int N = 200010; const int M = 10000; const int mod = 10007; int n , m ; struct Point { int x , y ;Point(){} }; struct Line{ int tag ; Point a, b ; }e[N]; inline bool cmp1 ( const Line &A , const Line &B ) { return A.a.x < B.a.x ; } inline bool cmp2 ( const Line &A , const Line &B ) { return A.a.y < B.a.y ; } int lazy[N<<2] , cnt[N<<2] , sum[N<<2] ; void build( int l , int r , int rt ) { sum[rt] = lazy[rt] = cnt[rt] = 0 ; if( l == r ) return ; int mid = (l+r)>>1; build(lson),build(rson); } void Up( int l , int r , int rt ) { if( cnt[rt] > 0 ) sum[rt] = r - l + 1 ; else sum[rt] = sum[lr] + sum[rr] ; } void update( int l , int r , int rt , int L , int R , int tag ) { if( l == L && r == R ) { if( tag ) { cnt[rt]++ , lazy[rt] ++ ; sum[rt] = r - l + 1 ; } else { cnt[rt]-- , lazy[rt] -- ; if( cnt[rt] > 0 ) sum[rt] = r - l + 1 ; else { if( l == r ) sum[rt] = 0 ; else sum[rt] = sum[lr] + sum[rr] ; } } return ; } int mid = (l+r)>>1; if( L > mid ) update(rson,L,R,tag); else if( R <= mid ) update(lson,L,R,tag); else update(lson,L,mid,tag) , update(rson,mid+1,R,tag); Up(l,r,rt); } int x1[N] , x2[N] , y1[N] , y2[N]; int main() { #ifdef LOCAL freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif // LOCAL int _ , cas = 1 ; int mx , Mx , my , My ; while( scanf("%d",&n) != EOF ) { Mx = My = -N , mx = my = N ; for( int i = 0 ; i < n ; ++i ) { scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]); mx = min( mx , x1[i] ); Mx = max( Mx , x2[i] ); my = min( my , y1[i] ); My = max( My , y2[i] ); e[i].a.x = x1[i] , e[i].a.y = y1[i] ; e[i].b.x = x1[i] , e[i].b.y = y2[i] ; e[i].tag = 1 ; e[i+n].a.x = x2[i] , e[i+n].a.y = y2[i]; e[i+n].b.x = x2[i] , e[i+n].b.y = y1[i]; e[i+n].tag = 0 ; } int tot = n * 2 ; sort( e , e + tot ,cmp1 ) ; LL ans = 0 , last = 0 ; build( my , My - 1 , 1 ); for( int i = 0 ; i < tot ; ++i ) { int x = e[i].a.y , y = e[i].b.y ; if( x > y ) swap(x,y); update( my , My - 1 , 1 , x , y -1 , e[i].tag ); LL tmp = sum[1] ; ans += abs( tmp - last ); last = tmp ; } for( int i = 0 ; i < n ; ++i ){ e[i].a.x = x1[i] , e[i].a.y = y1[i] ; e[i].b.x = x2[i] , e[i].b.y = y1[i] ; e[i].tag = 1 ; e[i+n].a.x = x2[i] , e[i+n].a.y = y2[i] ; e[i+n].b.x = x1[i] , e[i+n].b.y = y2[i] ; e[i+n].tag = 0 ; } last = 0 ; sort( e , e + tot , cmp2 ) ; build(mx,Mx-1,1); for( int i = 0 ; i < tot ; ++i ) { int x = e[i].a.x , y = e[i].b.x ; if( x > y ) swap(x,y); update( mx , Mx - 1 , 1 , x , y - 1 , e[i].tag ); LL tmp = sum[1] ; ans += abs( tmp - last ); last = tmp ; } printf("%I64d\n",ans); } }
原文:http://www.cnblogs.com/hlmark/p/4282525.html