Colourful Rectangle【扫描线】

We use Red, Green and Blue to make new colours. See the picture below:

Now give you n rectangles, the colour of them is red or green or blue. You have calculate the area of 7 different colour. (Note: A region may be covered by same colour several times, but it’s final colour depends on the kinds of different colour)

Input

The first line is an integer T(T <= 10), the number of test cases. The first line of each case contains a integer n (0 < n <= 10000), the number of rectangles. Then n lines follows. Each line start with a letter C(R means Red, G means Green, B means Blue) and four integers x1, y1, x2, y2(0 <= x1 < x2 < 10^9, 0 <= y1 < y2 < 10^9), the left-bottom's coordinate and the right-top's coordinate of a rectangle.

Output

For each case, output a line "Case a:", a is the case number starting from 1,then 7 lines, each line contain a integer, the area of each colour. (Note: You should print the areas as the order: R, G, B, RG, RB, GB, RGB).

Sample Input

Sample Output

Case 1:
3
3
0
1
0
0
0
Case 2:
4
4
12
4
4
4
4
Case 3:
0
12
15
0
0
0
0

挺好的一道题，一开始就想到了用状态压缩来写，毕竟就3种颜色，8个状态的说（还有个是最最最不容易引人注目的0状态！）而，这个0状态却是这道题目的重点了，一开始没想到，然后一直过不了样例……

我们分别用"001"、"010"、"100"三个二进制状态压缩得到的新的状态，然后分别去求各个状态对应的下面有多少颜色，但是，这道题却有些许不一样的地方，就是会存在用新的颜色覆盖掉之前的颜色，所以，我们就要进行些处理，就是每次更新的时候，就需要把目前节点的颜色全体清零，然后再进行运算，同时别忘了从0状态算起……不然总是少答案……

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 2e4 + 7;
int N, num, cnt_x, X[maxN], lazy[maxN<<2][3]; //每个点的颜色的对应数量
ll tree[maxN<<2][9], ans[9];
char op[3];
map<char, int> mp;
inline void dir() { mp['R'] = 0;    mp['G'] = 1;    mp['B'] = 2; }
struct node
{
    int lx, rx, y, val, color;
    node(int a=0, int b=0, int c=0, int d=0, int f=0):lx(a), rx(b), y(c), val(d), color(f) {}
}line[maxN];
bool cmp(node e1, node e2) { return e1.y < e2.y; }
inline void buildTree(int rt, int l, int r)
{
    memset(lazy[rt], 0, sizeof(lazy[rt]));
    memset(tree[rt], 0, sizeof(tree[rt]));
    if(l == r)
    {
        tree[rt][0] = X[r + 1] - X[l];
        return;
    }
    int mid = HalF;
    buildTree(Lson);
    buildTree(Rson);
    tree[rt][0] = tree[lsn][0] + tree[rsn][0];
}
void pushup(int rt, int l, int r)
{
    int state = 0;
    for(int i=0; i<3; i++) if(lazy[rt][i]) state |= (1<<i);
    memset(tree[rt], 0, sizeof(tree[rt]));
    if(l == r)
    {
        tree[rt][state] = X[r + 1] - X[l];
        return;
    }
    for(int i=0; i<=7; i++) tree[rt][state|i] += tree[lsn][i] + tree[rsn][i];
}
void update(int rt, int l, int r, int ql, int qr, int val, int color)
{
    if(ql <= l && qr >= r)
    {
        lazy[rt][color] += val;
        pushup(myself);
        return;
    }
    int mid = HalF;
    if(qr <= mid) update(QL, val, color);
    else if(ql > mid) update(QR, val, color);
    else { update(QL, val, color); update(QR, val, color); }
    pushup(myself);
}
inline void init()
{
    num = 0;    cnt_x = 1;
    memset(ans, 0, sizeof(ans));
}
int main()
{
    dir();
    int T;  scanf("%d", &T);
    for(int Cas=1; Cas<=T; Cas++)
    {
        init();
        scanf("%d", &N);
        for(int i=1; i<=N; i++)
        {
            scanf("%s", op);
            int lx, ly, rx, ry; scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
            line[++num] = node(lx, rx, ly, 1, mp[op[0]]);
            X[num] = lx;
            line[++num] = node(lx, rx, ry, -1, mp[op[0]]);
            X[num] = rx;
        }
        sort(X + 1, X + num + 1);
        for(int i=2; i<=num; i++) if(X[i] != X[i-1]) X[++cnt_x] = X[i];
        buildTree(1, 1, cnt_x);
        sort(line + 1, line + num + 1, cmp);
        for(int i=1; i<num; i++)
        {
            int l = (int)(lower_bound(X + 1, X + cnt_x + 1, line[i].lx) - X);
            int r = (int)(lower_bound(X + 1, X + cnt_x + 1, line[i].rx) - X - 1);
            update(1, 1, cnt_x, l, r, line[i].val, line[i].color);
            for(int color=1; color<=7; color++) ans[color] += tree[1][color] * (ll)(line[i+1].y - line[i].y);
        }
        printf("Case %d:\n", Cas);
        printf("%lld\n%lld\n%lld\n%lld\n%lld\n%lld\n%lld\n", ans[1], ans[2], ans[4], ans[3], ans[5], ans[6], ans[7]);
    }
    return 0;
}

Colourful Rectangle【扫描线】

相关推荐