FZU 2187 回家种地 ( 扫描线 + 离散求矩阵单次覆盖面积 )

2187 回家种地

Accept: 56 Submit: 230
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

小A毕业后，跑回家种地了。可是种地也不是简单的活，小A在播种的时候碰到难题了。

小
A承包了一块无限大的农田，他每次选取一块矩形区域播种。可是小A是个糊涂虫，他每次都忘记之前播种过的区域是哪一块，因此他就随机选择一个矩形区域播
种。如果一个区域被播种两次或者两次以上，因为种子之间的竞争，导致每个种子得到的资源都不够，无法顺利成长，因此长不出果实。

现在小A希望你帮他算算秋天的时候，能够长出庄稼的区域的面积。

Input

第一行给出一个整数T，表示测试样例的组数。

每个样例第一行有一个整数n，表示小A播种的矩形的个数。

接下来n行，每行有4个整数x1，y1，x2，y2，表示矩形的左下角和右上角。

1<=n<=10^5

0<=x1<x2<=10^8

0<=y1<y2<=10^8

Output

输出题目所求的面积，格式见样例。

Sample Input

0 0 10 10

1 1 2 2

0 0 1 1

1 1 2 2

Sample Output

Case 1: 99

Case 2: 2

离散后用map卡时，手写一个map然后注意一下结果爆 long long ~

做法是用覆盖大于1次减去覆盖大于0次的就求得等于1次的~

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

#include <iostream>

using namespace std;

#define root 1,(n<<1)+10,1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define lr rt<<1

#define rr rt<<1|1

const int N =  ;

const int M =  ;

struct HASHMAP {

    int head[M] , id[N] , next[N] , key[N] , tot ;

    void init() {

        memset( head , - , sizeof head );

        tot =  ;

    }

    void insert( int x , int idx ) {

        int u = x % M ;

        key[tot] = x ; id[tot] = idx ; next[tot] = head[u] ; head[u] = tot++ ;

    }

    int find( int x ) {

        int u = x % M ;

        for( int i = head[u] ; ~i ; i = next[i] ) {

            if( key[i] == x ) return id[i] ;

        }

    }

} mp ;

struct Point {

    int x , y1 , y2 , v ;

    bool operator < ( const Point &a ) const {

        return x < a.x ;

    }

}p[N];

int n , tot , tt , e[N] , c[N] ;

void addpoint( int x , int y1  ,int y2 , int v ) {

    p[tot].x = x , p[tot].y1 = y1 , p[tot].y2 = y2 , p[tot].v = v , tot++ ;

}

void lisan() {

    mp.init();

    sort( e , e + tt );

    int ntt =  ;

    for( int i =  ; i < tt ; ++i ) {

        if( e[i] != e[i-] ) e[ntt++] = e[i] ;

    }

    tt = ntt ;

    for( int i =  ; i < tt ; ++i ) {

        c[i+] = e[i] ;

        mp.insert( e[i] , i +  ) ;

    }

}

int cnt[N<<] , lazy[N<<] , date[N<<] ;

void build( int l , int r , int rt ) {

    cnt[rt] = lazy[rt] =  ;

    if( l == r ) {

        date[rt] = c[l+] - c[l];

        return ;

    }

    int mid = (l+r)>>;

    build(lson) , build(rson) ;

    date[rt] = date[lr] + date[rr];

}

void Down( int rt ) {

    if( lazy[rt] ) {

        cnt[lr] += lazy[rt] ;

        cnt[rr] += lazy[rt] ;

        lazy[lr] += lazy[rt] ;

        lazy[rr] += lazy[rt] ;

        lazy[rt] =  ;

    }

}

void Up( int rt ) {

    cnt[rt] = min( cnt[lr] , cnt[rr] );

}

void update( int l , int r , int rt , int L , int R , int v ) {

    if( l == L && r == R ) {

        cnt[rt] += v ; lazy[rt] += v ;

        return ;

    }

    int mid = (l+r)>> ;

    Down(rt) ;

    if( R <= mid ) update(lson,L,R,v) ;

    else if( L > mid ) update( rson,L,R,v);

    else update(lson,L,mid,v),update(rson,mid+,R,v);

    Up(rt);

}

int query1( int l , int r , int rt , int L , int R ) {

    if( cnt[rt] >  ) return date[rt] ;

    if( l == r ) return  ;

    Down(rt);

    int mid = (l+r)>>;

    if( R <= mid ) return  query1(lson,L,R);

    else if( L > mid ) return query1(rson,L,R);

    else return query1(lson,L,mid) + query1(rson,mid+,R);

}

int query0( int l , int r , int rt , int L , int R ) {

    if( cnt[rt] >  ) return date[rt] ;

    if( l == r ) return  ;

    Down(rt);

    int mid = (l+r)>>;

    if( R <= mid ) return  query0(lson,L,R);

    else if( L > mid ) return query0(rson,L,R);

    else return query0(lson,L,mid) + query0(rson,mid+,R);

}

int main() {

    #ifdef LOCAL

        freopen("in.txt","r",stdin);

    #endif // LOCAL

    int _ , cas =  ; scanf("%d",&_);

    while( _-- ) {

        printf("Case %d: ",cas++);

        scanf("%d",&n);

        tt = tot =  ;

        for( int i =  ; i < n ; ++i ) {

            int x1 , y1 , x2 , y2 ;

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            addpoint( x1 , y1 , y2 ,  );

            addpoint( x2 , y1 , y2 , - );

            e[tt++] = y1 ;

            e[tt++] = y2 ;

        }

        lisan();

        sort( p , p + tot ) ;

        build(,tt-,);

        long long ans =  ;

        update(,tt-,,mp.find(p[].y1),mp.find(p[].y2)-,p[].v);

        for( int i =  ; i < tot ; ++i ) {

            if( p[i].x != p[i-].x ) {

                ans += ( p[i].x - p[i-].x ) * 1LL * ( query0(,tt-,,,tt-) - query1(,tt-,,,tt-) ) ;

            }

            update(,tt-,,mp.find(p[i].y1),mp.find(p[i].y2)-,p[i].v);

        }

        cout << ans << endl ;

    }

    return  ;

}

种地

FZU 2187 回家种地 ( 扫描线 + 离散 求矩阵单次覆盖面积 )