hdu 4419 线段树 扫描线 离散化 矩形面积

 //离散化 + 扫描线 + 线段树
//这个线段树跟平常不太一样的地方在于记录了区间两个信息,len[i]表示颜色为i的被覆盖的长度为len[i], num[i]表示颜色i 『完全』覆盖了该区间几层。len[i]起传递儿子与父亲的关系,而num[i]不起传递作用,只是单纯的表示被覆盖的区间。
//然后就是pushUp函数,必须在update到底层后即更新num[]和len,然后把len传上去。
//离散化后由于求的是面积,所以我是把每条长度为1的线段当做一个点, 即把左端点表示此段长度。而不是把点当成点。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath> using namespace std;
#define lson l, m, rt<<1
#define rson m + 1, r, rt<<1|1
typedef long long ll;
const int maxn = 2e4 + ; struct Seg{
char c;
int y, s, t, tag;
}ss[maxn];
bool cmp(Seg a, Seg b){
return a.y < b.y;
}
int san[maxn], tot;
int num[maxn << ][],len[maxn << ][];
ll ans[];
void pushUp(int l, int r, int rt){
int state = (num[rt][] > ? : ) | (num[rt][] > ? : ) | (num[rt][] > ? : );
memset(len[rt], , sizeof(len[rt]));
if (state){
len[rt][state] = san[r] - san[l - ];
for (int i = ; i < ; ++i){
if (state != (state|i)){
int tmp = len[rt<<][i] + len[rt<<|][i];
len[rt][state|i] += tmp;
len[rt][state] -= tmp;
}
}
}
else if (l != r){
for (int i = ; i < ; ++i) len[rt][i] = len[rt<<][i] + len[rt<<|][i];
}
}
int getC(char c){
if (c == 'R') return ;
if (c == 'G') return ;
return ;
}
void update(int L, int R, char c, int tag, int l, int r, int rt){
if (L <= l && R >= r){
int cc = getC(c);
num[rt][cc] += tag;
//注意
pushUp(l, r, rt);
return ;
}
int m = (l + r) >> ;
if (L <= m) update(L, R, c, tag, lson);
if (R > m) update(L, R, c, tag, rson);
pushUp(l, r, rt);
}
int T, n;
int main(){
int tcas = ;
int x1, x2, y1, y2;
char s[];
scanf("%d", &T);
while (T--){
scanf("%d", &n);
tot = ;
for (int i = ; i <= n; ++i){
scanf("%s%d%d%d%d", s,&x1, &y1, &x2, &y2);
ss[i].c = s[]; ss[i].y = y1; ss[i].s = x1; ss[i].t = x2, ss[i].tag= ;
ss[i + n].c = s[]; ss[i + n].y = y2; ss[i + n].s = x1; ss[i + n].t = x2, ss[i + n].tag = -;
san[tot++] = x1 ; san[tot++] = x2;
}
n = n * ; sort(san, san + tot);
tot = unique(san, san + tot) - san;
sort(ss + , ss + n + , cmp);
ss[].y = ss[].y; memset(num, , sizeof(num));
memset(len, , sizeof(len));
memset(ans, , sizeof(ans));
for (int i = ; i <= n; ++i){
int l = lower_bound(san, san + tot, ss[i].s) - san + ;
int r = lower_bound(san, san + tot, ss[i].t) - san;
/*cout << " l = " << l << " r = " << r ;
cout << " tag = " << ss[i].tag << " c = "<< ss[i].c << endl;
for (int j = 1; j < 8; ++j) cout << len[1][j] << " ";
cout << endl;
cout << endl;
*/
if (ss[i].y != ss[i - ].y){
for (int j = ; j < ; ++j){
ans[j] += (ll)(ss[i].y - ss[i - ].y) * (ll)len[][j];
}
}
update(l, r, ss[i].c, ss[i].tag, , tot - , );
}
printf("Case %d:\n", ++tcas);
swap(ans[], ans[]);
for (int i = ; i < ; ++i)
printf("%lld\n", ans[i]);
}
return ;
}
上一篇:【数论·错位排列】bzoj4517 排列计数


下一篇:HDU 1542 Atlantis(线段树面积并)