本文共 3935 字，大约阅读时间需要 13 分钟。
2187 回家种地
小A毕业后，跑回家种地了。可是种地也不是简单的活，小A在播种的时候碰到难题了。
小 A承包了一块无限大的农田，他每次选取一块矩形区域播种。可是小A是个糊涂虫，他每次都忘记之前播种过的区域是哪一块，因此他就随机选择一个矩形区域播 种。如果一个区域被播种两次或者两次以上，因为种子之间的竞争，导致每个种子得到的资源都不够，无法顺利成长，因此长不出果实。
现在小A希望你帮他算算秋天的时候，能够长出庄稼的区域的面积。
第一行给出一个整数T，表示测试样例的组数。
每个样例第一行有一个整数n，表示小A播种的矩形的个数。
接下来n行，每行有4个整数x1，y1，x2，y2，表示矩形的左下角和右上角。
1<=n<=10^5
0<=x1<x2<=10^8
0<=y1<y2<=10^8
输出题目所求的面积，格式见样例。
离散后用map卡时 ， 手写一个map然后注意一下结果爆 long long ~
做法是用覆盖大于1次减去 覆盖大于0次的 就求得等于1次的~
#include #include #include #include #include #include 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|1const int N = 201000 ;const int M = 1000007 ;struct HASHMAP { int head[M] , id[N] , next[N] , key[N] , tot ; void init() { memset( head , -1 , sizeof head ); tot = 0 ; } 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 = 1 ; for( int i = 1 ; i < tt ; ++i ) { if( e[i] != e[i-1] ) e[ntt++] = e[i] ; } tt = ntt ; for( int i = 0 ; i < tt ; ++i ) { c[i+1] = e[i] ; mp.insert( e[i] , i + 1 ) ; }}int cnt[N<<2] , lazy[N<<2] , date[N<<2] ;void build( int l , int r , int rt ) { cnt[rt] = lazy[rt] = 0 ; if( l == r ) { date[rt] = c[l+1] - c[l]; return ; } int mid = (l+r)>>1; 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] = 0 ; }}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)>>1 ; 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+1,R,v); Up(rt);}int query1( int l , int r , int rt , int L , int R ) { if( cnt[rt] > 1 ) return date[rt] ; if( l == r ) return 0 ; Down(rt); int mid = (l+r)>>1; 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+1,R);}int query0( int l , int r , int rt , int L , int R ) { if( cnt[rt] > 0 ) return date[rt] ; if( l == r ) return 0 ; Down(rt); int mid = (l+r)>>1; 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+1,R);}int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int _ , cas = 1 ; scanf("%d",&_); while( _-- ) { printf("Case %d: ",cas++); scanf("%d",&n); tt = tot = 0 ; for( int i = 0 ; i < n ; ++i ) { int x1 , y1 , x2 , y2 ; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); addpoint( x1 , y1 , y2 , 1 ); addpoint( x2 , y1 , y2 , -1 ); e[tt++] = y1 ; e[tt++] = y2 ; } lisan(); sort( p , p + tot ) ; build(1,tt-1,1); long long ans = 0 ; update(1,tt-1,1,mp.find(p[0].y1),mp.find(p[0].y2)-1,p[0].v); for( int i = 1 ; i < tot ; ++i ) { if( p[i].x != p[i-1].x ) { ans += ( p[i].x - p[i-1].x ) * 1LL * ( query0(1,tt-1,1,1,tt-1) - query1(1,tt-1,1,1,tt-1) ) ; } update(1,tt-1,1,mp.find(p[i].y1),mp.find(p[i].y2)-1,p[i].v); } cout << ans << endl ; } return 0 ;}
转载于:https://www.cnblogs.com/hlmark/p/4367026.html
Problem Description
