AcWing 1228油漆面积题解（蓝桥杯线段树）
发布时间
阅读量：
阅读量
算法思想：就是将每个矩形的竖边依附于一条竖线，将这条竖线加入线段树中，并不断遍历这些竖线，利用线段树更新竖线上被矩形覆盖的长度，tr[1]记录的是当前竖线上被覆盖的总长度，len*记录的x之差就是这块矩形的面积，遍历所有竖线之后，就可以得出所有被矩形覆盖的面积
原题
大佬题解
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
struct Segment
{
int x, y1, y2; //x为横坐标，y1,y2为线段树维护的两个纵坐标
int k; //k表示我们要加的权值，为+1或-1
//由于要把所有的线段按照横坐标排序，所以要重载小于号
bool operator< (const Segment &t)const
{
return x < t.x;
}
}seg[N * 2]; //线段最多有两倍(每个矩形两条竖边)
全部评论 (0)
还没有任何评论哟~