一个咕咕咕了很久的算法, 众所周知扫描线就是维护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**/
}