HDU 4419 矩形面积并 - c++编程基础

这题貌似想法挺简单的。

跟普通的矩形并变形一下

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

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

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

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

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

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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;
sum[rt][3] = x[r + 1] - x[l];
}
else
{
sum[rt][7] = sum[lch(rt)][4] + sum[rch(rt)][4] + sum[lch(rt)][5] + sum[rch(rt)][5] + sum[lch(rt)][6] + sum[rch(rt)][6] + sum[lch(rt)][7] + sum[rch(rt)][7];
sum[rt][6] = 0;
sum[rt][5] = 0;
sum[rt][4] = 0;
sum[rt][3] = x[r + 1] - x[l] - sum[rt][7];
sum[rt][1] = sum[rt][2] = 0;
}
}
else if(cnt[rt] == 2)

HDU 4419 矩形面积并 (一)