Eternity

Until The End

扫描线

发表于 更新于 分类于 ，
本文字数： 2.7k 阅读时长 ≈ 2 分钟

“地毯式搜索”

P5490 扫描线

思路

用线段树维护一个横区间内所有的矩形个数，对于每个不为 $0$ 的区间则计算答案。

因为坐标过大，所以线段树维护的是离散化之后的坐标。

在扫描线算法中，我们总共需要两次排序：将端点的横坐标排序和横线的纵坐标排序。在进行排序之后，我们还需要将端点横坐标离散化和去重，用 $STL$ 的 $unique$ 函数就可以了。

最后，扫描横边，查询每一个横边所在区间的竖边即可。

参考资料：赵悦岑’s blog’

AC Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
struct Segment_Tree
{
    int l,r,dat;
    ll tag;
}Tree[MAXN<<2];
struct Sort_Str
{
    ll l,r,dat;
    int tag;
}Num[MAXN<<2];
int n,m;
ll b[MAXN<<4],l1,l2,r1,r2;
inline bool underCmp(Sort_Str a,Sort_Str b)
{
    return a.dat<b.dat;
}
inline void underPushUp(int p)
{
    if(Tree[p].dat) Tree[p].tag=b[Tree[p].r+1]-b[Tree[p].l];
    else Tree[p].tag=Tree[p<<1].tag+Tree[p<<1|1].tag;
}
inline void underBuild(int p,int l,int r)
{
    Tree[p].l=l,Tree[p].r=r,Tree[p].tag=Tree[p].dat=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    underBuild(p<<1,l,mid),underBuild(p<<1|1,mid+1,r);
}
inline void underAdd(int p,ll l,ll r,int k)
{
    if(b[Tree[p].l]>=r||b[Tree[p].r+1]<=l) return ;
    if(b[Tree[p].l]>=l&&b[Tree[p].r+1]<=r)
    {
        Tree[p].dat+=k;
        underPushUp(p);
        return ;
    }
    underAdd(p<<1,l,r,k),underAdd(p<<1|1,l,r,k);
    underPushUp(p);
}
int main()
{
    // freopen("segmenttree.in","r",stdin);
    // freopen("segmenttree.out","w",stdout);
    underRead(n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
        Num[(i<<1)-1]=(Sort_Str){l1,l2,r1,1};
        Num[i<<1]=(Sort_Str){l1,l2,r2,-1};
        b[(i<<1)-1]=l1,b[i<<1]=l2;
    }
    n<<=1;
    sort(Num+1,Num+1+n,underCmp);
    sort(b+1,b+1+n);
    m=unique(b+1,b+n+1)-(b+1);
    underBuild(1,1,m-1);
    ll s=0;
    for(int i=1;i<n;++i)
    {
        underAdd(1,Num[i].l,Num[i].r,Num[i].tag);
        s+=Tree[1].tag*(Num[i+1].dat-Num[i].dat);
        // printf("%d %d\n",Tree[1].tag,(Num[i+1].dat-Num[i].dat));
    }
    printf("%lld",s);
    return 0;
}
/*
2
100 100 200 200
150 150 250 255
*/
相关文章