這題貌似想法挺簡單的。
跟普通的矩形並變形一下
把三種顏色分別對應一個二進制位，那麼用十進制數表示 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;
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)
{
if(l == r)
{
for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
sum[rt][2] = x[r + 1] - x[l];
}
else
{
sum[rt][7] = sum[lch(rt)][5] + sum[rch(rt)][5] + sum[lch(rt)][7] + sum[rch(rt)][7];
sum[rt][6] = sum[lch(rt)][4] + sum[rch(rt)][4] + sum[lch(rt)][6] + sum[rch(rt)][6];
sum[rt][5] = 0;
sum[rt][4] = 0;
sum[rt][3] = sum[lch(rt)][1] + sum[rch(rt)][1] + sum[lch(rt)][3] + sum[rch(rt)][3];
sum[rt][2] = x[r + 1] - x[l] - sum[rt][7] - sum[rt][6] - sum[rt][3];
sum[rt][1] = 0;
}
}
else if(cnt[rt] == 1)
{
if(l == r)
{
for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
sum[rt][1] = x[r + 1] - x[l];
}
else
{
sum[rt][7] = sum[lch(rt)][7] + sum[rch(rt)][7] + sum[lch(rt)][6] + sum[rch(rt)][6];
sum[rt][6] = 0;
sum[rt][5] = sum[lch(rt)][4] + sum[rch(rt)][4] + sum[lch(rt)][5] + sum[rch(rt)][5];
sum[rt][4] = 0;
sum[rt][3] = sum[lch(rt)][2] + sum[rch(rt)][2] + sum[lch(rt)][3] + sum[rch(rt)][3];
sum[rt][2] = 0;
sum[rt][1] = x[r + 1] - x[l] - sum[rt][7] - sum[rt][5] - sum[rt][3];
}
}
else
{
if(l == r)
{
for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
}
else
{
for(int i = 1; i <= 7; i++) sum[rt][i] = sum[lch(rt)][i] + sum[rch(rt)][i];
}
}
}
void update(int L, int R, int v, int l, int r, int rt)
{
if(L <= l && R >= r)
{
if(v > 0)cnt[rt] |= v, num[rt][v]++;
else
{
v = -v;
if(cnt[rt] & v)
{
num[rt][v]--;
if(num[rt][v] == 0)cnt[rt] = cnt[rt] ^ v;
}
}
up(rt, l, r);
return;
}
int m = (l + r) >> 1;
if(L <= m) update(L, R, v, lson);
if(R > m) update(L, R, v, rson);
up(rt, l, r);
}
int main()
{
int T;
scanf("%d", &T);
int cas = 0;
while(T--)
{
memset(ans, 0, sizeof(ans));
memset(sum, 0, sizeof(sum));
memset(cnt, 0, sizeof(cnt));
memset(num, 0, sizeof(num));
int m = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%s%I64d%I64d%I64d%I64d", p[i].op, &p[i].lx, &p[i].ly, &p[i].rx, &p[i].ry);
x[m] = p[i].lx;
seg[m++] = Seg(get(p[i].op), p[i].lx, p[i].rx, p[i].ly, 1);
x[m] = p[i].rx;
seg[m++] = Seg(-get(p[i].op), p[i].lx, p[i].rx, p[i].ry, -1);
}
sort(x, x + m);
sort(seg, seg + m);
int kx = unique(x, x + m) - x;
for(int i = 0; i < m - 1; i++)
{
int l = bin(0, kx - 1, seg[i].l);
int r = bin(0, kx - 1, seg[i].r) - 1;
if(l <= r){
update(l, r, seg[i].co, 0, kx - 1, 1);
}
for(int j = 1; j <= 7; j++)
ans[j] += sum[1][j] * (seg[i + 1].h - seg[i].h) ;
}
printf("Case %d:\n", ++cas);
printf("%I64d\n", ans[1]);
printf("%I64d\n", ans[2]);
printf("%I64d\n", ans[4]);
printf("%I64d\n", ans[3]);
printf("%I64d\n", ans[5]);
printf("%I64d\n", ans[6]);
printf("%I64d\n", ans[7]);
}
return 0;
}
#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;
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)
{
if(l == r)
{
for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
sum[rt][2] = x[r + 1] - x[l];
}
else
{
sum[rt][7] = sum[lch(rt)][5] + sum[rch(rt)][5] + sum[lch(rt)][7] + sum[rch(rt)][7];
sum[rt][6] = sum[lch(rt)][4] + sum[rch(rt)][4] + sum[lch(rt)][6] + sum[rch(rt)][6];
sum[rt][5] = 0;
sum[rt][4] = 0;
sum[rt][3] = sum[lch(rt)][1] + sum[rch(rt)][1] + sum[lch(rt)][3] + sum[rch(rt)][3];
sum[rt][2] = x[r + 1] - x[l] - sum[rt][7] - sum[rt][6] - sum[rt][3];
sum[rt][1] = 0;
}
}
else if(cnt[rt] == 1)
{
if(l == r)
{
for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
sum[rt][1] = x[r + 1] - x[l];
}
else
{
sum[rt][7] = sum[lch(rt)][7] + sum[rch(rt)][7] + sum[lch(rt)][6] + sum[rch(rt)][6];
sum[rt][6] = 0;
sum[rt][5] = sum[lch(rt)][4] + sum[rch(rt)][4] + sum[lch(rt)][5] + sum[rch(rt)][5];
sum[rt][4] = 0;
sum[rt][3] = sum[lch(rt)][2] + sum[rch(rt)][2] + sum[lch(rt)][3] + sum[rch(rt)][3];
sum[rt][2] = 0;
sum[rt][1] = x[r + 1] - x[l] - sum[rt][7] - sum[rt][5] - sum[rt][3];
}
}
else
{
if(l == r)
{
for(int i = 1; i <= 7; i++) sum[rt][i] = 0;
}
else
{
for(int i = 1; i <= 7; i++) sum[rt][i] = sum[lch(rt)][i] + sum[rch(rt)][i];
}
}
}
void update(int L, int R, int v, int l, int r, int rt)
{
if(L <= l && R >= r)
{
if(v > 0)cnt[rt] |= v, num[rt][v]++;
else
{
v = -v;
if(cnt[rt] & v)
{
num[rt][v]--;
if(num[rt][v] == 0)cnt[rt] = cnt[rt] ^ v;
}
}
up(rt, l, r);
return;
}
int m = (l + r) >> 1;
if(L <= m) update(L, R, v, lson);
if(R > m) update(L, R, v, rson);
up(rt, l, r);
}
int main()
{
int T;
scanf("%d", &T);
int cas = 0;
while(T--)
{
memset(ans, 0, sizeof(ans));
memset(sum, 0, sizeof(sum));
memset(cnt, 0, sizeof(cnt));
memset(num, 0, sizeof(num));
int m = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%s%I64d%I64d%I64d%I64d", p[i].op, &p[i].lx, &p[i].ly, &p[i].rx, &p[i].ry);
x[m] = p[i].lx;
seg[m++] = Seg(get(p[i].op), p[i].lx, p[i].rx, p[i].ly, 1);
x[m] = p[i].rx;
seg[m++] = Seg(-get(p[i].op), p[i].lx, p[i].rx, p[i].ry, -1);
}
sort(x, x + m);
sort(seg, seg + m);
int kx = unique(x, x + m) - x;
for(int i = 0; i < m - 1; i++)
{
int l = bin(0, kx - 1, seg[i].l);
int r = bin(0, kx - 1, seg[i].r) - 1;
if(l <= r){
update(l, r, seg[i].co, 0, kx - 1, 1);
}
for(int j = 1; j <= 7; j++)
ans[j] += sum[1][j] * (seg[i + 1].h - seg[i].h) ;
}
printf("Case %d:\n", ++cas);
printf("%I64d\n", ans[1]);
printf("%I64d\n", ans[2]);
printf("%I64d\n", ans[4]);
printf("%I64d\n", ans[3]);
printf("%I64d\n", ans[5]);
printf("%I64d\n", ans[6]);
printf("%I64d\n", ans[7]);
}
return 0;
}
