作用:
1.计算若干个矩形覆盖的面积
2.普通的线段树区间更新,查询可以将某一段的每个点的权都当成1查询
3.麻烦,不懂了,之后再更新
板板:
//6_5-线段树(扫描线)
//////////////
int n;
typedef double tp;
tp xs[maxn * 2];//记录x坐标
int num_x;
struct opt
{
tp t1, t2;
tp y1;
int y2;
int x1, x2;
bool operator<(opt ri)const
{
return y1 < ri.y1;
}
}ops[maxn * 2];//记录操作,就是不同的Y
int num_op;
int tonu(tp x)
{
return lower_bound(xs + 1, xs + 1 + num_x, x) - xs;
}
#define ls (o<<1)
#define rs (o<<1|1)
#define mid ((e[o].l+e[o].r)>>1)
struct node
{
int l, r;
int cnt;
tp len;
};
node e[(maxn * 2) << 2];
inline void PushUp(int &o)
//TODO: 根据子节点更新父节点
{
if (e[o].cnt) e[o].len = xs[e[o].r + 1] - xs[e[o].l];
else
{
if (e[o].l == e[o].r) e[o].len = 0;
else e[o].len = e[ls].len + e[rs].len;
}
}
void build(int o, int l, int r)
{
//TODO: 初始化lazy和sum
e[o].l = l; e[o].r = r; e[o].len = e[o].cnt = 0;
if (l == r) { /*e[o].sum = a[l]*/; return; }
build(ls, l, mid);
build(rs, mid + 1, r);
PushUp(o);
}
void S_T(int o, ll inc)//update from new inc and update my lazy S_T: solve and tag
{
//TODO: 根据情景完成自身区间的改变,将改变参数传递给下一代
e[o].cnt += inc;
PushUp(o);
}
void update(int o, int l, int r, int v)//区间加v
{
if (l > r)return;
if (e[o].l == l && e[o].r == r) { S_T(o, v); return; }//找到边缘
update(ls, max(e[ls].l, l), min(r, mid), v);
update(rs, max(mid + 1, l), min(e[rs].r, r), v);
PushUp(o);
}
tp solve(int n)//返回覆盖矩形区域的面积
{
tp ans = 0; num_op = 0; num_x = 0;
RE2(i, n)
{
//TODO:
tp x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
xs[++num_x] = x1; xs[++num_x] = x2;//记录x
ops[++num_op] = { x1,x2,y1,1,inf,inf };//记录操作
ops[++num_op] = { x1,x2,y2,-1,inf,inf };
}
//调整xs
sort(xs + 1, xs + 1 + num_x);
num_x = unique(xs + 1, xs + 1 + num_x) - (xs + 1);
//初始化ops
RE2(i, num_op)ops[i].x1 = tonu(ops[i].t1), ops[i].x2 = tonu(ops[i].t2);
sort(ops + 1, ops + 1 + num_op);
ops[n * 2 + 1] = { inf,inf,inf,inf,inf,inf };
build(1, 1, num_x);
RE2(i, num_op)
{
update(1, ops[i].x1, ops[i].x2 - 1, ops[i].y2);
if (i != num_op)ans += e[1].len*(ops[i + 1].y1 - ops[i].y1);
}
return ans;
}
//////////////