题目描述

算法（线段树 +扫描线）（告诉我这个蒟蒻这是简单我真的不信）

扫描线的话，书上有，蒟蒻就不误人子弟了。主要是针对一些蒟蒻本人容易写错的点记录一下

1.本题运用扫描线的话，可以参考亚特兰蒂斯，主要就是，线段树其实维护的是每两个点之间的距离，所以建树的时候与一般的维护点的线段树有点不一样，并且，记录的时候，假设我们要记录三个点，那么其实，放在线段树里面的其实是这样子$[1,2]和[2,3]$,就是像这样有点重合,因为只有这样,才能把每一个区间都记录下来

2.关于值的记录与更新.首先,线段树节点$l$和$r$记录离散化后的$y$值,$dat$a记录当前区间被覆盖的长度,$add$记录当前区间被==完全覆盖==的次数。这样子我们在更新的时候，看看$add$的值是否为0,为0就把data更新为两个子节点的值之和,反之就为当前区间对应的长度

3.排列的时候,除了按照$x$的值从小到大排序,还要按照记录的$flag$的值排,因为有可能有两个矩形,一个矩形A的末尾刚好与另一个B的开始相接,这个时候我们认为它并没有出现新的需要加入最终答案的边,所以我们要先把B这个矩形加进来,这样就不会重复计算

4.关于如何统计,其实就是每次加入一个边之后,答案加上$abs(上一次的边和-这一次的边和)$,以及和统计面积不一样的是,这个题,要先从左往右扫一遍扫描线算y,再从下到上扫一遍x(当然这是蒟蒻的头脑中唯一能想出的暴力做法,如果有大佬有其他的方法欢迎留言)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define s1(x) x << 1
#define s2(x) (x << 1) + 1
#define LL long long
const int N = 5005;
struct linetree{
    int l,r,dat,add;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define d(x) t[x].dat
    #define add(x) t[x].add//这是用来统计被覆盖了多少次的
}t[N << 3];

struct point{
    int x,y1,y2,flag;//flag用来存左边还是右边,左边存1,右边存-1
}pt[N << 1];//这是用来存点的
int temp[N][4];//这也是用来存点的,用来更新第二次扫x时的值
int val[N << 1];//用来离散化的
int n;
bool com(point a,point b)
{
    if(a.x < b.x)
    return a.x < b.x;
    else if(a.x == b.x && a.flag > b.flag) return true;//这里记得判断flag大的放在前面加
    return false;
}
void build(int p,int l,int r)
{
    l(p) = l;
    r(p) = r;
    d(p) = 0;
    add(p) = 0;//建树的时候记得清空,不然第二次扫x的时候会错
    if(r == l + 1)
        return ;//这里的建树注意一下
    int mid = (l + r) >> 1;
    build(s1(p),l,mid);
    build(s2(p),mid,r);
}
void pushup(int p)
{
    if(add(p)) d(p) = val[r(p)] - val[l(p)];
    else d(p) = d(s1(p)) + d(s2(p));//更新
}
void change(int p,int l,int r,int x)
{
    if(l <= l(p) && r >= r(p))
    {
        add(p) += x;
        pushup(p);
        return ;
    }
    if(l < r(s1(p))) change(s1(p),l,r,x);
    if(r > l(s2(p))) change(s2(p),l,r,x);
    pushup(p);
    return ;
}
int get_ans()
{
    sort(val + 1,val + (n << 1) + 1);
    int cnt = unique(val + 1,val + (n << 1) + 1) - (val + 1);//离散化+去重排序,但是这道题数据比较小,应该不离散也可以??

    build(1,1,cnt);//建树

    sort(pt + 1,pt + (n << 1) + 1,com);

    int ans = 0,last = 0;//ans存答案,last存上一次加边后的长度

    int l = lower_bound(val + 1,val + cnt + 1,pt[1].y1) - val;
    int r = lower_bound(val + 1,val + cnt + 1,pt[1].y2) - val;

    <!--change(1,l,r,pt[1].flag);-->
    <!--ans += abs(last - d(1));-->
    <!--last = d(1);-->
    for(int i = 1;i <= (n << 1);++ i)
    {
        int l = lower_bound(val + 1,val + cnt + 1,pt[i].y1) - val;
        int r = lower_bound(val + 1,val + cnt + 1,pt[i].y2) - val;//查找y对应的离散后的值
        change(1,l,r,pt[i].flag);
        ans += abs(last - d(1));//记得是加绝对值
//      cout << ans << endl;
        last = d(1);//更新last
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n; ++ i)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);

        pt[i].x = a;
        pt[i + n].x = c;
        pt[i].y1 = pt[i + n].y1 = b;
        pt[i].y2 = pt[i + n].y2 = d;
        pt[i].flag = 1;
        pt[i + n].flag = -1;

        val[i] = b;
        val[i + n] = d;
        temp[i][0] = a;
        temp[i][1] = b;
        temp[i][2] = c;
        temp[i][3] = d;
    }

    int ans = 0;
    ans = get_ans();//扫y

    for(int i = 1;i <= n;++ i)
    {
        int a = temp[i][1];
        int b = temp[i][0];
        int c = temp[i][3];
        int d = temp[i][2];

        pt[i].x = a;
        pt[i + n].x = c;
        pt[i].y1 = pt[i + n].y1 = b;
        pt[i].y2 = pt[i + n].y2 = d;
        pt[i].flag = 1;
        pt[i + n].flag = -1;

        val[i] = d;
        val[i + n] = b;
    }
    ans += get_ans();扫x
    cout << ans;
    return 0;
}