我觉得要注意的几点
1 我的模板线段树的叶子节点存的都是 x[L]~x[L+1]
2 如果没有必要这个lazy 标志是可以不下传的 也就省了一个push_down
3 注意push_up 写法有点不一样，不过是可以改成一样的。
简单裸题*2
L - Atlantis HDU - 1542
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = ;
double v[maxn];
struct node {
double l, r, h;
int d;
node(double l = , double r = , double h = , int d = ) :l(l), r(r), h(h), d(d) {}
}line[maxn];
bool cmp(node a, node b) {
return a.h < b.h;
}
double sum[maxn * ];
int lazy[maxn * ];
void build(int id, int l, int r) {
sum[id] = ;
lazy[id] = ;
if (l == r) return;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
} void push_up(int id, int l, int r) {
if (lazy[id]) sum[id] = v[r + ] - v[l];
else sum[id] = sum[id << ] + sum[id << | ];
} void update(int id, int l, int r, int x, int y, int d) {
if (x <= l && y >= r) {
lazy[id] += d;
push_up(id, l, r);
return;
}
int mid = (l + r) >> ;
if (x <= mid) update(id << , l, mid, x, y, d);
if (y > mid) update(id << | , mid + , r, x, y, d);
push_up(id, l, r);
} int main() {
int n, cas = ;
while (scanf("%d", &n) != EOF && n) {
int cnt = , tot = ;
for (int i = ; i <= n; i++) {
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
v[++cnt] = x1, v[++cnt] = x2;
line[++tot] = node(x1, x2, y1, ), line[++tot] = node(x1, x2, y2, -);
}
sort(v + , v + + cnt);
sort(line + , line + + tot, cmp);
int len = unique(v + , v + + cnt) - v - ;
double ans = ;
build(, , len - );
for (int i = ; i < tot; i++)//这里注意只需要要tot-1即可，因为我们每次都是按底算的
{
int l = lower_bound(v + , v + + len, line[i].l) - v;
int r = lower_bound(v + , v + + len, line[i].r) - v - ;
update(, , len - , l, r, line[i].d);
ans += sum[] * (line[i + ].h - line[i].h);
}
printf("Test case #%d\n", ++cas);
printf("Total explored area: %.2lf\n\n", ans);
}
return ;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 8e4 + ;
ll v[maxn];
struct node {
ll l, r, h;
int d;
node(ll l = , ll r = , ll h = , int d = ) :l(l), r(r), h(h), d(d) {}
}line[maxn];
bool cmp(node a, node b) {
return a.h < b.h;
}
ll sum[maxn * ];
int lazy[maxn * ];
void build(int id, int l, int r) {
sum[id] = ;
lazy[id] = ;
if (l == r) return;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
} void push_up(int id, int l, int r) {
if (lazy[id]) sum[id] = v[r + ] - v[l];
else sum[id] = sum[id << ] + sum[id << | ];
} void update(int id, int l, int r, int x, int y, int d) {
if (y<l || x>r) return;
// printf("id=%d l=%d r=%d x=%d y=%d\n", id, l, r, x, y);
if (x <= l && y >= r) {
lazy[id] += d;
if (lazy[id]) sum[id] = v[r + ] - v[l];
else sum[id] = sum[id << ] + sum[id << | ];
return;
}
int mid = (l + r) >> ;
if (x <= mid) update(id << , l, mid, x, y, d);
if (y > mid) update(id << | , mid + , r, x, y, d);
push_up(id, l, r);
} int main() {
int n, cnt = , tot = ;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
ll l, r, h;
scanf("%lld%lld%lld", &l, &r, &h);
v[++cnt] = l, v[++cnt] = r;
line[++tot] = node(l, r, , ), line[++tot] = node(l, r, h, -);
}
sort(v + , v + + cnt);
sort(line + , line + + tot, cmp);
int len = unique(v + , v + + cnt) - v - ;
build(, , len - );
ll ans = ;
for (int i = ; i < tot; i++) {
int l = lower_bound(v + , v + + len, line[i].l) - v;
int r = lower_bound(v + , v + + len, line[i].r) - v - ;
// printf("l=%d r=%d\n", l, r);
update(, , len - , l, r, line[i].d);
ans += sum[] * (line[i + ].h - line[i].h);
// printf("%lld %lld ans=%lld %lld sum=%lld\n", line[i].l, line[i].r, ans, line[i].h, sum[1]);
// printf("%lld %lld ans=%lld %lld\n", line[i + 1].l, line[i + 1].r, ans, line[i + 1].h);
// printf("\n\n");
}
printf("%lld\n", ans);
return ;
}
然后就是一个没有这么简单的裸题，比较暴力。
这个是给每一个y轴都建一棵线段树，每一个y轴代表 y[L]~y[L+1]
然后每次对于这个矩形的每一个y轴的这一段都查一下，然后如果已经被覆盖了，就删去这一段，然后更新这一段。
这个题目其实还是很好写的，但是要注意push_down的写法。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = ;
struct rect
{
int x1, y1, x2, y2, col;
rect(int x1=,int y1=,int x2=,int y2=,int col=):x1(x1),y1(y1),x2(x2),y2(y2),col(col){}
}ex[maxn]; int vx[maxn * ], vy[maxn * ], color[maxn];
int sum[maxn][maxn * ], lazy[maxn][maxn * ]; void build(int i,int id,int l,int r)
{
sum[i][id] = lazy[i][id] = ;
if (l == r) return;
int mid = (l + r) >> ;
build( i,id << , l, mid);
build(i, id << | , mid + , r);
} void push_up(int i,int id)
{
sum[i][id] = sum[i][id << ] + sum[i][id << | ];
// printf("sum[%d][%d]=%d\n", i, id, sum[i][id]);
} void push_down(int i,int id,int l,int r)
{
if (lazy[i][id] == ) return;
int mid = (l + r) >> ;
sum[i][id << ] = vx[mid + ] - vx[l];
sum[i][id << | ] = vx[r + ] - vx[mid + ];
lazy[i][id << ] = lazy[i][id << | ] = lazy[i][id];
// printf("l=%d r=%d mid=%d\n", l, r, mid);
// printf("x sum[%d][%d]=%d\n", i, id<<1, sum[i][id<<1]);
// printf("x sum[%d][%d]=%d\n", i, id<<1|1, sum[i][id<<1|1]);
lazy[i][id] = ;
} void update(int i,int id,int l,int r,int x,int y)
{
if (x <= l && y >= r) {
sum[i][id] = vx[r + ] - vx[l];
// printf("l=%d r=%d\n", l, r);
// printf("ww sum[%d][%d]=%d\n", i, id, sum[i][id]);
lazy[i][id] = ;
return;
}
int mid = (l + r) >> ;
push_down(i, id, l, r);
if (x <= mid) update(i, id << , l, mid, x, y);
if (y > mid) update(i, id << | , mid + , r, x, y);
push_up(i, id);
} int query(int i,int id,int l,int r,int x,int y)
{
if (x <= l && y >= r) return sum[i][id];
int mid = (l + r) >> , ans = ;
push_down(i, id, l, r);
if (x <= mid) ans += query(i, id << , l, mid, x, y);
if (y > mid) ans += query(i, id << | , mid + , r, x, y);
return ans;
} int main()
{
int w, h, n, cas = ;
while (scanf("%d%d", &w, &h) && (w + h)) {
memset(color, , sizeof(color));
int tot = , cnt = ;
scanf("%d", &n);
vx[++tot] = , vx[++tot] = w;
vy[++cnt] = , vy[++cnt] = h;
for (int i = ; i <= n; i++) {
int x1, y1, x2, y2, col;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &col);
ex[i] = rect(x1, y1, x2, y2, col);
vx[++tot] = x1, vx[++tot] = x2;
vy[++cnt] = y1, vy[++cnt] = y2;
}
sort(vx + , vx + + tot);
sort(vy + , vy + + cnt);
int lenx = unique(vx + , vx + + tot) - vx - ;
int leny = unique(vy + , vy + + cnt) - vy - ;
// for (int i = 1; i <= lenx; i++) printf("vx[%d]=%d\n", i, vx[i]);
for (int i = ; i < leny; i++) build(i, , , lenx - );
for (int i = n; i >= ; i--) {
// printf("i=%d\n", i);
int col = ex[i].col;
int ans = (ex[i].x2 - ex[i].x1)*(ex[i].y2 - ex[i].y1);
int lx = lower_bound(vx + , vx + + lenx, ex[i].x1) - vx;
int ly = lower_bound(vy + , vy + + leny, ex[i].y1) - vy;
int rx = lower_bound(vx + , vx + + lenx, ex[i].x2) - vx - ;
int ry = lower_bound(vy + , vy + + leny, ex[i].y2) - vy - ;
for (int j = ly; j <= ry; j++) {
int res = query(j, , , lenx - , lx, rx);
ans -= (vy[j + ] - vy[j])*res;
// printf("j=%d\n", j);
// printf("lx=%d ly=%d rx=%d ry=%d\n", lx, ly, rx, ry);
// printf("x1=%d y1=%d x2=%d y2=%d\n", ex[i].x1, ex[i].y1, ex[i].x2, ex[i].y2);
// printf("res=%d %d ans=%d\n", res, vy[j + 1] - vy[j],ans);
update(j, , , lenx - , lx, rx);
}
color[col] += ans;
// printf("color[%d]=%d\n", col, color[col]);
// printf("\n");
}
int num = ;
if (cas) printf("\n");
printf("Case %d:\n", ++cas);
for (int i = ; i <= ; i++) {
if (color[i]) {
printf("%d %d\n", i, color[i]);
num++;
}
}
if (num == ) printf("There is %d color left on the wall.\n", num);
else printf("There are %d colors left on the wall.\n", num);
}
return ;
}
/*
10 8
4
1 9 5 10 9
1 8 2 9 8
7 1 10 8 4
6 2 9 6 4
0 0 */