UVA 11983 Weird Advertisement（线段树求矩形并的面积）-白红宇

UVA 11983 Weird Advertisement（线段树求矩形并的面积）

阅读量：4994 次

发布时间：2019-06-12

本文共 4247 字，大约阅读时间需要 14 分钟。

题目大意是说给你N个矩形，让你求被覆盖k次以上的点的总个数(x,y<1e9)

首先这个题有一个转化，吧每个矩形的x2,y2+1这样就转化为了求N个矩形被覆盖k次以上的区域的面积

由于坐标很大，首先考虑的就是将坐标离散化，然后建立线段树tree[][K]，表示x的某个区间被覆盖了K次（大于K次算K次）的实际长度，在计算时把矩形转化为一系列横线段（就是说将一个矩形拆开为两条线段，下面的标记为1,上面的标记为-1（这里的标记很有技巧）），然后将这些线段按照y值的从小到达排序（y值相同的按照标记为-1的排在前，为1的排在后）

然后考虑从下往上依次拿出第一条线段(x1, x2, y, flag)，将x1, x2整个区间tree[x1,x2][1]更新为x1到x2覆盖了1次的实际长度，之后每取出一条线段先计算与上一条线段的高度差，乘上整个区间被覆盖K次的总长度，便的到了当前覆盖K次的结果，然后按照当前线段的flag值更新线段树

若flag=1说明它是一条起始边，说明后面的x1,x2这个区间被覆盖的次数加1，更新线段树x1,x2区间被覆盖k次(0<k<=K)的总长+[x1, x2]的实际长度

若flag=-1说说明这是一条结束边，x1,x2这个区间的被覆盖次数应当-1,所以与上面相反，减去这个区间的实际长度即可

同时由于y相同的是先算的-1的线段，保证了这个矩形没有继续和后方的矩形继续相交，所以结果是准确的

不理解时可以按照思路画一个图模拟一下，便可以很好理解

1 #include   2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                 
                   14 using namespace std; 15 #define INF 1e9 16 #define inf (-((LL)1<<40)) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 template
                  
                    T CMP_MIN(T a, T b) { return a < b; } 25 template
                   
                     T CMP_MAX(T a, T b) { return a > b; } 26 template
                    
                      T MAX(T a, T b) { return a > b ? a : b; } 27 template
                     
                       T MIN(T a, T b) { return a < b ? a : b; } 28 template
                      
                        T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 29 template
                       
                         T LCM(T a, T b) { return a / GCD(a,b) * b; } 30 31 //typedef __int64 LL; 32 typedef long long LL; 33 const int MAXN = 30005; 34 const int MAXM = 100005; 35 const double eps = 1e-10; 36 const int MOD = 9901; 37 38 int N, K, T; 39 LL Hash[MAXN<<1], cntHash; 40 int cnt[MAXN<<3], len[MAXN<<3][12]; 41 struct Line { 42 LL x1, x2, y; 43 int flag; 44 Line(){} 45 Line(LL _x1, LL _x2, LL _y, int _flag) 46 { 47 x1 = _x1; 48 x2 = _x2; 49 y = _y; 50 flag = _flag; 51 } 52 bool operator < (const Line& A)const 53 { 54 if(y != A.y) return y < A.y; 55 return flag < A.flag; 56 } 57 }line[MAXN<<1]; 58 59 int bsearch(int low, int high, int num) 60 { 61 while(low <= high) 62 { 63 int mid = (low + high) >> 1; 64 if(Hash[mid] == num) return mid; 65 if(Hash[mid] > num) high = mid - 1; 66 else low = mid + 1; 67 } 68 return 0; 69 } 70 71 void buildTree(int k, int L, int R) 72 { 73 cnt[k] = 0; mem0(len[k]); 74 75 len[k][0] = Hash[R+1] - Hash[L]; 76 77 if(L == R) return ; 78 79 int mid = (L + R) >> 1; 80 81 buildTree(lson); buildTree(rson); 82 } 83 84 void updateCur(int k, int L, int R) 85 { 86 mem0(len[k]); 87 if(cnt[k] >= K) 88 len[k][K] = Hash[R+1] - Hash[L]; 89 else if(L == R) 90 len[k][cnt[k]] = Hash[R+1] - Hash[L]; 91 else { 92 for(int i=cnt[k];i<=K;i++) 93 len[k][i] += len[k<<1][i-cnt[k]] + len[k<<1|1][i-cnt[k]]; 94 for(int i=K-cnt[k]+1;i<=K;i++) 95 len[k][K] += len[k<<1][i] + len[k<<1|1][i]; 96 } 97 } 98 99 void update(int k, int L, int R, int l, int r, int flag)100 {101 if(R < l || r < L) return ;102 103 if(l<=L && R<=r) { cnt[k] += flag; updateCur(k, L, R); return ; }104 105 int mid = (L + R) >> 1;106 107 update(lson, l, r, flag); update(rson, l, r, flag);108 109 updateCur(k, L, R);110 }111 112 void init()113 {114 int x1, x2, y1, y2;115 scanf("%d %d", &N, &K);116 for(int i=1;i<=N;i++)117 {118 scanf("%d %d %d %d", &x1, &y1, &x2, &y2);119 ++ x2; ++ y2;120 line[i] = Line(x1, x2, y1, 1);121 line[i+N] = Line(x1, x2, y2, -1);122 Hash[i] = x1;123 Hash[i+N] = x2;124 }125 sort(line + 1, line + 2*N + 1);126 127 sort(Hash + 1, Hash + 2*N + 1);128 cntHash = 0;129 for(int i = 1; i <= N*2; i ++ )130 if(i==1 || Hash[i-1] != Hash[i])131 Hash[++cntHash] = Hash[i];132 133 buildTree(1, 1, cntHash-1);134 }135 136 int main()137 {138 //FOPENIN("in.txt");139 scanf("%d", &T);140 for(int t = 1; t <= T; t ++ )141 {142 init();143 LL ans = 0;144 for(int i = 1; i <= 2 * N; i ++ )145 {146 if(i != 1)147 {148 ans += (line[i].y - line[i-1].y) * len[1][K];149 }150 int l = bsearch(1, cntHash, line[i].x1);151 int r = bsearch(1, cntHash, line[i].x2);152 update(1, 1, cntHash-1, l, r-1, line[i].flag);153 }154 155 printf("Case %d: %lld\n", t, ans);156 }157 return 0;158 }

转载于:https://www.cnblogs.com/gj-Acit/p/3886551.html

你可能感兴趣的文章