HDU 4052 Adding New Machine (线段树+离散化)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4052

初始给你w*h的矩阵，给你n个矩形(互不相交)，按这些矩形尺寸把初始的矩形扣掉，形成一个新的'矩形'。然后给你1*m大小的矩形，问这个矩形在新'矩形'中有多少种放法。

一开始没想法==，然后看了看题解，说是线段树做的。

要是m为1的话，那答案就是剩下的面积了。

不为1的话，可以把n个矩形的面积扩展一下(我是向右扩展)，比如x1 y1 x2 y2 的矩形扣掉，就相当于x1 y1 x2+m-1 y2的地方扣掉了，这种是x轴的情况。那么y轴的情况就是x1 y1 x2 y2+m-1。最左边也要扣掉，比如x轴就是0 0 m - 1 h。所以最后就是算剩下的面积了。(我的方法比较笨，就是x轴一个线段树扫一下，y轴一个线段树扫一下)

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <map>

 using namespace std;

 const int MAXN = 1e5 + ;

 typedef long long LL;

 LL fab(LL a) {

     return (a >  ? a : -a);

 }

 struct data {

     int ll , rr , flag , l , r , h;

     bool operator <(const data &cmp) const {

         return h < cmp.h;

     }

 }line1[MAXN] , line2[MAXN];

 struct segtree {

     LL val;

     int l , r , add;

 }T1[MAXN * ] , T2[MAXN * ];

 LL x[MAXN] , y[MAXN];

 map <int , int> mp1 , mp2;

 int f1 , f2;

 inline void add1(LL num) {

     if(!mp1[num]) {

         x[++f1] = num;

         mp1[num] = ;

     }

 }

 inline void add2(LL num) {

     if(!mp2[num]) {

         y[++f2] = num;

         mp2[num] = ;

     }

 }

 void pushupx(int p) {

     if(T1[p].add) {

         T1[p].val = x[T1[p].r] - x[T1[p].l];

     }

     else if(T1[p].r - T1[p].l == ) {

         T1[p].val = ;

     }

     else {

         T1[p].val = T1[p << ].val + T1[(p << )|].val;

     }

 }

 void pushupy(int p) {

     if(T2[p].add) {

         T2[p].val = y[T2[p].r] - y[T2[p].l];

     }

     else if(T2[p].r - T2[p].l == ) {

         T2[p].val = ;

     }

     else {

         T2[p].val = T2[p << ].val + T2[(p << )|].val;

     }

 }

 void buildx(int p , int l , int r) {

     int mid = (l + r) >> ;

     T1[p].l = l , T1[p].r = r , T1[p].val = T1[p].add = ;

     if(r - l == ) {

         return ;

     }

     buildx(p <<  , l , mid);

     buildx((p << )| , mid , r);

 }

 void buildy(int p , int l , int r) {

     int mid = (l + r) >> ;

     T2[p].l = l , T2[p].r = r , T2[p].val = T2[p].add = ;

     if(r - l == ) {

         return ;

     }

     buildy(p <<  , l , mid);

     buildy((p << )| , mid , r);

 }

 void updatex(int p , int l , int r , int add) {

     int mid = (T1[p].l + T1[p].r) >> ;

     if(T1[p].l == l && T1[p].r == r) {

         T1[p].add += add;

         pushupx(p);

         return ;

     }

     if(r <= mid) {

         updatex(p <<  , l , r , add);

     }

     else if(l >= mid) {

         updatex((p << )| , l , r , add);

     }

     else {

         updatex(p <<  , l , mid , add);

         updatex((p << )| , mid , r , add);

     }

     pushupx(p);

 }

 void updatey(int p , int l , int r , int add) {

     int mid = (T2[p].l + T2[p].r) >> ;

     if(T2[p].l == l && T2[p].r == r) {

         T2[p].add += add;

         pushupy(p);

         return ;

     }

     if(r <= mid) {

         updatey(p <<  , l , r , add);

     }

     else if(l >= mid) {

         updatey((p << )| , l , r , add);

     }

     else {

         updatey(p <<  , l , mid , add);

         updatey((p << )| , mid , r , add);

     }

     pushupy(p);

 }

 int main()

 {

     LL w , h , n , m , x1 , x2 , y1 , y2;

     while(~scanf("%lld %lld %lld %lld" , &w , &h , &n , &m)) {

         mp1.clear();

         mp2.clear();

         f1 = f2 = ;

         if(m == ) {

             LL sum = ;

             while(n--) {

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

                 sum += (fab(x1 - x2) + ) * (fab(y1 - y2) + );

             }

             printf("%lld\n" , h * w - sum);

             continue;

         }

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

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

             x1-- , y1--;

             int ls = i <<  , rs = (i << )|;

             line1[ls].l = x1 , line1[ls].r = min(w , x2 + m - ) , line1[ls].h = y1 , line1[ls].flag = ;

             line1[rs].l = x1 , line1[rs].r = line1[ls].r , line1[rs].h = y2 , line1[rs].flag = -;

             line2[ls].l = y1 , line2[ls].r = min(h , y2 + m - ) , line2[ls].h = x1 , line2[ls].flag = ;

             line2[rs].l = y1 , line2[rs].r = line2[ls].r , line2[rs].h = x2 , line2[rs].flag = -;

             add1(line1[ls].l);

             add1(line1[ls].r);

             add1(line1[rs].l);

             add1(line1[rs].r);

             add2(line2[ls].l);

             add2(line2[ls].r);

             add2(line2[rs].l);

             add2(line2[rs].r);

         }

         int ls = n <<  , rs = (n << )| , f = ((n << )|) + ;

         line1[ls].l =  , line1[ls].r = m -  , line1[ls].h =  , line1[ls].flag = ;

         line1[rs].l =  , line1[rs].r = m -  , line1[rs].h = h , line1[rs].flag = -;

         line2[ls].l =  , line2[ls].r = m -  , line2[ls].h =  , line2[ls].flag = ;

         line2[rs].l =  , line2[rs].r = m -  , line2[rs].h = w , line2[rs].flag = -;

         add1(line1[ls].l);

         add1(line1[ls].r);

         add1(line1[rs].l);

         add1(line1[rs].r);

         add2(line2[ls].l);

         add2(line2[ls].r);

         add2(line2[rs].l);

         add2(line2[rs].r);

         sort(line1 , line1 + f);

         sort(line2 , line2 + f);

         sort(x +  , x + f1 + );

         sort(y +  , y + f2 + );

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

             line1[i].ll = lower_bound(x +  , x + f1 +  , line1[i].l) - x;

             line1[i].rr = lower_bound(x +  , x + f1 +  , line1[i].r) - x;

             line2[i].ll = lower_bound(y +  , y + f2 +  , line2[i].l) - y;

             line2[i].rr = lower_bound(y +  , y + f2 +  , line2[i].r) - y;

         }

         LL res1 =  , res2 = ;

         buildx( ,  , f1);

         buildy( ,  , f2);

         updatex( , line1[].ll , line1[].rr , line1[].flag);

         updatey( , line2[].ll , line2[].rr , line2[].flag);

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

             res1 += (line1[i].h - line1[i - ].h) * T1[].val;

             res2 += (line2[i].h - line2[i - ].h) * T2[].val;

             updatex( , line1[i].ll , line1[i].rr , line1[i].flag);

             updatey( , line2[i].ll , line2[i].rr , line2[i].flag);

         }

         printf("%lld\n" , h * w *  - res1 - res2);

     }

 }

巴特西

HDU 4052 Adding New Machine (线段树+离散化)

最新文章

热门文章