这里是一级标题
分割线下面是我原准备发的博客,然而事实是:
大概一年以前 通过书籍理解了扫描线的基本原理
5-19 花一小时抄了oi-wiki的代码,疑惑于长还是宽,由于把数组改成指针,过不了样例
5-20 又花了一小时抄了一遍,改了几个bug,知道了区间维护要求build[M,R],过不了样例
5-21 花了三小时理解代码、看其他的博客、重构代码、写博客梳理代码、过了样例,后全WA,手造样例WA、再次修改原理、AC手造样例,再次全WA,然后放弃
2021-5-20 && 2021-5-21,这两个爱你爱你我爱你
的日子就在一点也不可爱的扫描线中度过了,无果,寻病终,最后得出结论:我只适合背代码。
所以代码还是错的,我还是不会。
哪个好心人给我讲讲原理和细节或者帮着看一下最终的代码/kl/kl/kl/kl
QAQ
--------------------分割线---------------------
这里是正文的一级标题
OI-wiki上讲的是线段树维护长,给出的代码却是维护的宽,误导了我好久。
我的做法是线段树维护长,用p
维护给出的所有横向边(也就是矩形的长)。
扫描线从下往上扫,每个矩形下面的长是这个矩形加入的线段,遇到就加入线段树,上面的长是这个矩形退出的线段,遇到就退出线段树,上/下用flg
表示,其值为0/1
那么加入和退出的操作就等价于+flg
。
把所有的线段处理好后就无所谓属于哪个矩形了,也就是线段独立存在了,这时候我们按纵坐标给其排序,从下往上逐条处理即可。
获得排序后,此时每条线段在哪个纵坐标上也就没用了,因为我们维护的是扫描线,是一条二维的线。
所有矩形的面积并也就被分为了一个个单独横条,横条的宽度即为相邻两条线段之间的距离p[i] - p[i - 1]
。
核心操作就是用线段树rot
维护区间[min_x, max_x]
上的线段长度,然后乘上长条宽度累计入答案。
线段
维护纵坐标在y
上的一条线段[x1, x2]
bool cmp(line a, line b){
if(a.y == b.y) return a.flg < b.flg;//注意先出后进
return a.y < b.y;
}
struct line{
int y, x1, x2, flg;
}p[maxn * 2];
线段树
节点维护的信息是[l, r]
这个区间里当前存在的长度。
struct node{
int l, r, lazy, sum;
node *ls, *rs;
}Mem[maxn * 4], *pool = Mem;
离散化:
所有的横坐标放进num[]
里然后sort
,用[1, n * 2]
作为线段树的定义域,根据num[]
访问到真正的坐标值,放进node
的l和r
作为真正的定义域,也就是维护的区间。
离散化就决定了在建树的时候左右孩子的递归就要是这样的:
M = L + R >> 1;
u->ls = build(L, M);
u->rs = build(M, R);//而不是build(M + 1, R)
u->pushup();
这样才能保证num[M]
到num[M + 1]
这段区间不被漏掉。
注意到这个lazy
是说区间[num[l], num[r]]
这里面的线段出现了几次,因为这个区间可能被多条矩形的下边都加入了线段树,退出的时候每次只能退出一条,而只有当所有矩形的上边都退出了时候,这段区间的线段才真正不存在了,不然就是一直要算入答案的。
事实上,lazy
只在当前用到的线段树的最下面一层节点(一定要是表示num[i]~num[i+1]这么基本的节点)才有用,其余节点是没有出现次数这一说的,只用维护sum
就好了。
所以非叶节点的lazy = 0, sum > 0
的情况是合法的。
这也决定了pushdown
函数是不必要的。注意我们用的是EqualRange()
而不是InRange()
也就是说懒标记在这里并不适用,所有的基本线段都要维护。
现在我们来看看upd(x1, x2, flg)
的操作,这个操作的对象是线段。
inline bool EqualRange(const int L, const int R){
return (L == l) && (r == R);
}
inline bool OutofRange(const int L, const int R){
return (L >= r) || (l >= R);
}
inline void maketag(const int flg){
lazy += flg;
if(lazy <= 0) sum = 0;
if(lazy > 0) sum = r - l;
}
inline void pushup(){
sum = 0;
if(ls != NULL) sum += ls->sum;
if(rs != NULL) sum += rs->sum;
}
inline void pushdown(){
if(ls != NULL) {
ls->maketag(lazy);
}
if(rs != NULL) rs->maketag(lazy);
lazy = 0;
}
inline void upd(const int x1, const int x2, const int flg){
if(EqualRange(x1, x2)){
maketag(flg);
}
else if(!OutofRange(x1, x2)){
pushdown();
if(ls != NULL) if(x1 < ls->r)ls->upd(x1, min(x2, ls->r), flg);
if(rs != NULL) if(x2 > rs->l)rs->upd(max(x1, rs->l), x2, flg);
pushup();
}
}
现在来强调最最最最重要的一个bug点,我在这里卡了一个小时。是OutofRange(L, R)
函数。这个是基本函数了,由于是区间,端点的重合并不真的是在区间里,所以要加上等号!!!
对:
inline bool OutofRange(const int L, const int R){
return (L >= r) || (l >= R);
}
错:
inline bool OutofRange(const int L, const int R){
return (L > r) || (l > R);
}
把上面的int全改为longlong后仍旧WA的假code(TAT
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define mod 998244353
using namespace std;
int rd(){
int res = 0, fl = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') fl = -1;
c = getchar();
}
while(isdigit(c)){
res = (res << 3) + (res << 1) + c - '0';
c = getchar();
}
return res * fl;
}
namespace force{
int main(){
return 0;
}
}
const int maxn = 100010;
struct line{
ll y, x1, x2, flg;
}p[maxn * 2];
int n;
int num[maxn * 2];
ll ans;
struct Node{
ll l, r, sum, lazy;
Node *ls, *rs;
inline bool EqualRange(const ll L, const ll R){
return (L == l) && (r == R);
}
inline bool OutofRange(const ll L, const ll R){
return (L >= r) || (l >= R);
}
inline void maketag(const ll flg){
lazy += flg;
if(lazy <= 0) sum = 0;
if(lazy > 0) sum = r - l;
}
inline void pushup(){
sum = 0;
if(ls != NULL) sum += ls->sum;
if(rs != NULL) sum += rs->sum;
}
inline void pushdown(){
if(ls != NULL) {
ls->maketag(lazy);
}
if(rs != NULL) rs->maketag(lazy);
lazy = 0;
}
inline void upd(const ll x1, const ll x2, const ll flg){
if(EqualRange(x1, x2)){
maketag(flg);
}
else if(!OutofRange(x1, x2)){
pushdown();
if(ls != NULL) if(x1 < ls->r)ls->upd(x1, min(x2, ls->r), flg);
if(rs != NULL) if(x2 > rs->l)rs->upd(max(x1, rs->l), x2, flg);
pushup();
}
// printf("[%d,%d], lazy=%d, sum=%d\n", l, r, lazy, sum);
}
}Mem[maxn * 4], *pool = Mem;
Node* New(){
return ++pool;
}
Node* build(const int L, const int R){
Node *u = New();
u->lazy = 0;
u->l = num[L];
u->r = num[R];
if(R - L <= 1){
u->sum = 0;
}
else{
int M = L + R >> 1;
u->ls = build(L, M);
u->rs = build(M, R);
u->pushup();
}
return u;
}
bool cmp(line a, line b){
if(a.y == b.y) return a.flg < b.flg;
return a.y < b.y;
}
int main(){
n = rd();
int x1, x2, y1, y2;
for(int i = 1; i <= n; ++i){
x1 = rd(); y1 = rd(); x2 = rd(); y2 = rd();
p[i].y = y1;
p[i].x1 = x1;
p[i].x2 = x2;
p[i].flg = 1;
p[i + n].y = y2;
p[i + n].x1 = x1;
p[i + n].x2 = x2;
p[i + n].flg = -1;
num[i] = x1;
num[i + n] = x2;
}
sort(num + 1, num + 1 + 2 * n);
sort(p + 1, p + 1 + 2 * n, cmp);
Node *rot = build(1, 2 * n);
rot->upd(p[1].x1, p[1].x2, p[1].flg);
// printf("sum %d\n", rot->sum);
for(int i = 2; i <= n * 2; ++i){
// printf("line: %d %d\n", p[i].x1, p[i].x2);
ans += (p[i].y - p[i - 1].y) * (rot->sum);
rot->upd(p[i].x1, p[i].x2, p[i].flg);
// printf("sum %d\n", rot->sum);
}
printf("%lld\n", ans);
return 0;
}
/*
3
100 100 150 150
150 150 200 200
200 200 250 255
*/