[学习笔记]线段树六 扫描线

一个咕咕咕了很久的算法, 众所周知扫描线就是维护y轴(或x轴)同时存在的的线段的总长度, 然后按照x轴从大到小的遍历x,很容易就能想清楚,对于一个按顺序排列的x,每次我都可以跳这一段距离,而不会导致中间的某一个区域突然需要增加或删除y轴的总长度

模板问题,求一个矩形坐标均为整数的矩形面积并

不过因为普通的线段树用来维护扫描线可能会导致一些问题,因此会将线段树做一下修改

对于建树操作, 我们对每一段区间赋值按照存在的数值来赋值. (按照下标来复制也是可以的)

对于每一个结点将会存在的左右儿子的区间范围设置为 l, mid 和 mid, r 注意这里并不是 mid + 1, r,因为l~mid和mid+1~r中间会有mid~mid+1中间的线段无法记录,

因为对于扫描线的线段树我们用到的会是线段信息,因此我们会对线段树保存的都是线段,没有点值

void build(int l, int r, int k){
    a[k].l = v[l], a[k].r = v[r];
    if(r - l <= 1) return ; // 若不是线段可以不用要
    int mid = l + r >> 1;
    build(l, mid, k << 1);
    build(mid, r, k << 1|1);
}

对于所有矩形操作,我可以按照x坐标排序,这样的话我的操作就可以是从左向右依次修改的,

首先矩形的面积是可以通过划分成一小块一小块的更小的矩形,来求和相加的.

因此我就可以根据x_i每次对应找到上一个x轴的坐标x_{i-1},那么他们直接的差值就是长,而线段树中的长度就是高, 这样直接长*高就是在(x_i - x_{i-1}) * a[1].len, 其中a[1].len表示长度可以不连续,

因此考虑更新y轴所在线段是就是一个问题

void query(int k, int l, int r, int x){ // x为1表示区间[l, r]增加了一层, x为-1表示删除了一层
    if(l <= a[k].l && a[k].r <= r ){
        a[k].c += x; // 距离区间被覆盖多少层
        pushup(k); // 更新该区间的长度
        return ;
    }
    if(l < a[k << 1].r) query(k << 1, l, r, x);
    if(r > a[k << 1|1].l) query(k << 1|1, l, r, x);
    pushup(k); // 对应修改必然要更新该节点状态
}

对面上述代码基本上和线段树普通的代码相似, 对应a[k].c就是普通线段是的lazy标记,相当于记录者这个l~r中间一共保存多少线段

同样借鉴线段是的pushdown可以得到pushup的写法

void pushup(int k){
    if(a[k].c) a[k].len = a[k].r - a[k].l; // 这个只需要维护底层就好,上面的一定会通过下面的代码传上去的
    else a[k].len = a[k << 1].len + a[k << 1|1].len;
} 下附完整代码
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define eps 1e-9
#define endl '\n'
#define gcd __gcd
#define pi acos(-1)
#define ll long long
#define LL long long
#define IDX(x) x - 'A'
#define idx(x) x - 'a'
#define idz(x) x - '0'
#define ld long double
#define lowebit(x) x&(-x)
#define rint register int
#define Len(x) (int)(x).size()
#define all(s) (s).begin(), (s).end()
using namespace std;
inline int read()
{
	register int x = 0, f = 1, ch = getchar();
	while( !isdigit(ch) ){if(ch == '-') f = -1; ch = getchar();}
	while( isdigit(ch) ){x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}
const int maxn = 1e6 + 5;
int v[maxn << 1];
struct L
{
    int x, y1, y2, s;
    bool operator < (const L xx)const {return x < xx.x;}
}len[maxn << 1];
struct node
{
    int l, r, c;
    ll len ;
}a[maxn << 3];

void push(int k)
{
    if(a[k].c) a[k].len = a[k].r - a[k].l;
    else a[k].len = a[k << 1].len + a[k << 1|1].len;
}
void build(int l, int r, int k)
{
    a[k].l = v[l]; a[k].r = v[r];
    if(r - l <= 1) return ;
    int mid = l + r >> 1;
    build(l, mid, k << 1);
    build(mid, r, k << 1|1);
}
void query(int x, int y, int z, int k)
{
    if(a[k].l >= x && a[k].r <= y)
    {
        a[k].c += z;
        push(k);
        return ;
    }
    if(x < a[k << 1].r) query(x, y, z, k << 1);
    if(y > a[k << 1|1].l) query(x, y, z, k << 1|1);
    push(k);
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    clock_t c1ockck = clock();
    int n; cin >> n;
    for(int i = 1 ; i <= n ; i ++)
    {
        int x, y, z, k;cin >> x >> y >> z >> k;
        len[i] = (L){x, y, k, 1};
        len[i + n] = (L){z, y, k, -1};
        v[i] = y;
        v[i + n] = k;
    }
    sort(v + 1, v + 1 + 2 * n);
    sort(len + 1, len + 1 + 2 * n);
    build(1, 2 * n, 1);
    ll ans = 0;
    for(int i = 1 ; i <= n * 2 ; i ++)
    {
        ans += a[1].len * (len[i].x - len[i - 1].x);
        query(len[i].y1, len[i].y2, len[i].s, 1);
    }
    cout << ans << endl;
    cerr << endl << "Time:" << clock() - c1ockck << "ms" <<endl;
    /**srO**/return 0;/**Orz**/
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注