HDU 4419 矩形面积并

这题貌似想法挺简单的。

跟普通的矩形并变形一下

把三种颜色分别对应一个二进制位，那么用十进制数表示 R, G, B, RG, RB, GB, RGB

就是 1,2,4,3,5,6,7

然后在pushup操作中把这些东西更新一下就行了

注意，普通矩形并是一条线段表示进入矩形，另一条表示出了矩形，那么本题中就对三种颜色分别记录了

当时比赛的时候写的比较蛋疼。完全是码农写法。其实完全可以写的很精简。

[cpp]
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define MAXN 41111
#define MAXM 555555
#define INF 1000000011
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int n;
struct REC
{
    long long lx, rx, ly, ry;
    char op[5];
} p[MAXN];
struct Seg
{
    long long l, r, h;
    int co;
    int s;
    Seg() {}
    Seg(int xx, long long a, long long b, long long c, int d)
    {
        co = xx;
        l = a;
        r = b;
        h = c;
        s = d;
    }
    bool operator <(const Seg &cmp)const
    {
        if(cmp.h == h) return co < cmp.co;
        return h < cmp.h;
    }
} seg[MAXN * 2];
long long x[MAXN * 2];
int bin(int low, int high, long long v)
{
    while(low <= high)
    {
        int mid = (low + high) >> 1;
        if(x[mid] == v) return mid;
        else if(x[mid] > v) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}
long long sum[4 * MAXN][9];
int cnt[4 * MAXN];
int num[4 * MAXN][5];
long long ans[9];
int get(char *s)
{
    if(s[0] == 'R') return 1;
    if(s[0] == 'G') return 2;
    if(s[0] == 'B') return 4;
}
void up(int rt, int l, int r)
{
    if(cnt[rt] == 7)
    {
        for(int i = 1; i <= 6; i++) sum[rt][i] = 0;
        sum[rt][7] = x[r + 1] - x[l];
    }
    else if(cnt[rt] == 6)
    {
        if(l == r)
        {
            for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
            sum[rt][6] = x[r + 1] - x[l];
        }
        else
        {
            sum[rt][7] = sum[lch(rt)][1] + sum[rch(rt)][1] + sum[lch(rt)][3] + sum[rch(rt)][3] + sum[lch(rt)][5] + sum[rch(rt)][5] + sum[lch(rt)][7] + sum[rch(rt)][7];
            sum[rt][6] = x[r + 1] - x[l] - sum[rt][7];
            for(int i = 1; i <= 5; i++) sum[rt][i] = 0;
        }
    }
    else if(cnt[rt] == 5)
    {
        if(l == r)
        {
            for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
            sum[rt][5] = x[r + 1] - x[l];
        }
        else
        {
            sum[rt][7] = sum[lch(rt)][2] + sum[rch(rt)][2] + sum[lch(rt)][3] + sum[rch(rt)][3] + sum[lch(rt)][6] + sum[rch(rt)][6] + sum[lch(rt)][7] + sum[rch(rt)][7];
            sum[rt][6] = 0;
            sum[rt][5] = x[r + 1] - x[l] - sum[rt][7];
            for(int i = 1; i <= 4; i++) sum[rt][i] = 0;
        }
    }
    else if(cnt[rt] == 4)
    {
        if(l == r)
        {
            for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
            sum[rt][4] = x[r + 1] - x[l];
        }
        else
        {
            sum[rt][7] = sum[lch(rt)][3] + sum[rch(rt)][3] + sum[lch(rt)][7] + sum[rch(rt)][7];
            sum[rt][6] = sum[lch(rt)][2] + sum[rch(rt)][2] + sum[lch(rt)][6] + sum[rch(rt)][6];
            sum[rt][5] = sum[lch(rt)][1] + sum[rch(rt)][1] + sum[lch(rt)][5] + sum[rch(rt)][5];
            sum[rt][4] = x[r + 1] - x[l] - sum[rt][7] - sum[rt][6] - sum[rt][5];
            for(int i =1 ; i <= 3; i++) sum[rt][i] = 0;
        }
    }
    else if(cnt[rt] == 3)
    {
        if(l == r)
        {
            for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
     &nb

补充：软件开发 , C++ ,