Colourful Rectangle【扫描线】

佚名 5年前 (2019-05-28) 算法 2039人围观抢沙发百度已收录

很明显的可以发现是一个扫描线的问题，但是怎么处理区域呢，发现只有三种颜色，也就是最多也就是7种状态，那么我们可以进行一个状态压缩即可。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

但是，在向上pushup的时候，存在我们要以子树的状态来向上推，也就意味着一开始的目前节点是要去清空的，然后再去更新其覆盖的线长。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 #include <string>
  5 #include <cstring>
  6 #include <algorithm>
  7 #include <limits>
  8 #include <vector>
  9 #include <stack>
 10 #include <queue>
 11 #include <set>
 12 #include <map>
 13 #define lowbit(x) ( x&(-x) )
 14 #define pi 3.141592653589793
 15 #define e 2.718281828459045
 16 #define INF 0x3f3f3f3f
 17 #define HalF (l + r)>>1
 18 #define lsn rt<<1
 19 #define rsn rt<<1|1
 20 #define Lson lsn, l, mid
 21 #define Rson rsn, mid+1, r
 22 #define QL Lson, ql, qr
 23 #define QR Rson, ql, qr
 24 #define myself rt, l, r
 25 using namespace std;
 26 typedef unsigned long long ull;
 27 typedef long long ll;
 28 const int maxN = 1e4 + 7;
 29 int N, tot, _UP;
 30 ll X[maxN<<1], ans[8];
 31 struct node
 32 {
 33     ll lx, rx, y;
 34     int typ, val;
 35     node(ll a=0, ll b=0, ll c=0, int f=0, int d=0):lx(a), rx(b), y(c), typ(f), val(d) {}
 36 }line[maxN<<1];
 37 bool cmp(node e1, node e2) { return e1.y < e2.y; }
 38 struct Tree
 39 {
 40     int siz[4];
 41     ll col[8];
 42     void clear() { memset(siz, 0, sizeof(siz)); memset(col, 0, sizeof(col)); }
 43 }t[maxN<<3];
 44 inline void pushup(int rt, int l, int r)
 45 {
 46     memset(t[rt].col, 0, sizeof(t[rt].col));
 47     int state = 0;
 48     for(int i=1; i<=3; i++) if(t[rt].siz[i]) state |= (1<<(i - 1));
 49     if(l == r) t[rt].col[state] = X[r + 1] - X[l];
 50     else for(int i=0; i<=7; i++) { t[rt].col[i|state] += t[lsn].col[i] + t[rsn].col[i]; }
 51 }
 52 inline void buildTree(int rt, int l, int r)
 53 {
 54     t[rt].clear();
 55     if(l == r) { t[rt].col[0] = X[r + 1] - X[l]; return; }
 56     int mid = HalF;
 57     buildTree(Lson);
 58     buildTree(Rson);
 59     t[rt].col[0] = t[lsn].col[0] + t[rsn].col[0];
 60 }
 61 inline void update(int rt, int l, int r, int ql, int qr, int typ, int val)
 62 {
 63     if(ql <= l && qr >= r)
 64     {
 65         t[rt].siz[typ] += val;
 66         pushup(myself);
 67         return;
 68     }
 69     int mid = HalF;
 70     if(qr <= mid) update(QL, typ, val);
 71     else if(ql > mid) update(QR, typ, val);
 72     else { update(QL, typ, val); update(QR, typ, val); }
 73     pushup(myself);
 74 }
 75 inline void init()
 76 {
 77     tot = 0;
 78     memset(ans, 0, sizeof(ans));
 79 }
 80 char s[5];
 81 int main()
 82 {
 83     int T;  scanf("%d", &T);
 84     for(int Cas=1; Cas<=T; Cas++)
 85     {
 86         scanf("%d", &N);
 87         init();
 88         ll lx, ly, rx, ry;
 89         for(int i=1, tmp; i<=N; i++)
 90         {
 91             scanf("%s%lld%lld%lld%lld", s, &lx, &ly, &rx, &ry);
 92             if(s[0] == 'R') tmp = 1;
 93             else if(s[0] == 'G') tmp = 2;
 94             else tmp = 3;
 95             line[++tot] = node(lx, rx, ly, tmp, 1);
 96             X[tot] = lx;
 97             line[++tot] = node(lx, rx, ry, tmp, -1);
 98             X[tot] = rx;
 99         }
100         sort(X + 1, X + tot + 1);
101         sort(line + 1, line + tot + 1, cmp);
102         _UP = (int)(unique(X + 1, X + tot + 1) - X - 1);
103         buildTree(1, 1, _UP);
104         for(int i=1, l, r; i<tot; i++)
105         {
106             l  =(int)(lower_bound(X + 1, X + _UP + 1, line[i].lx) - X);
107             r = (int)(lower_bound(X + 1, X + _UP + 1, line[i].rx) - X - 1);
108             update(1, 1, _UP, l, r, line[i].typ, line[i].val);
109             for(int col=1; col<=7; col++) ans[col] += (line[i + 1].y - line[i].y) * t[1].col[col];
110         }
111         swap(ans[3], ans[4]);
112         printf("Case %d:\n", Cas);
113         for(int i=1; i<=7; i++) printf("%lld\n", ans[i]);
114     }
115     return 0;
116 }