前言

这篇相比上篇简单太多了……虽然这样，感觉扫描线的思想还是很有用的。

一、包含每个查询的最小区间

class Solution {
public:

    typedef pair<int,int> pii;

    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        int n=intervals.size();
        int m=queries.size();

        //根据开头位置从小到大排序
        sort(intervals.begin(),intervals.end());

        vector<pii>q(m);
        for(int i=0;i<m;i++)
        {
            q[i].first=queries[i];
            q[i].second=i;
        }

        //查询从小到大排序
        sort(q.begin(),q.end());
    
        //小根堆维护区间长度
        priority_queue<pii,vector<pii>,greater<pii>>pq;

        vector<int>ans(m);
        for(int i=0,j=0,line=0;i<m;i++)
        {
            //扫描线
            line=q[i].first;
            
            //扫描线穿过的区间入堆
            while(j<n&&intervals[j][0]<=line)
            {
                pq.push({intervals[j][1]-intervals[j][0]+1,intervals[j][1]});
                
                j++;
            }

            //“懒删除”堆 -> 当脏数据跑到堆顶再删
            while(!pq.empty()&&pq.top().second<line)
            {
                pq.pop();
            }

            if(!pq.empty())
            {
                ans[q[i].second]=pq.top().first;
            }
            else
            {
                ans[q[i].second]=-1;
            }
        }

        return ans;
    }
};

这个题的思路其实很简单，首先考虑先对每个区间根据左端点从小到大排序，然后再对每条查询从小到大排序。那么之后就可以根据查询从小到大依次扫过去，中间用一个小根堆维护区间长度。所以当扫描线更新后，先让所有被穿过的区间入堆，然后再删除右端点已经过期的区间，所以此时堆顶的区间就是长度最小的区间。这里注意，即使堆内有过期的区间也不要紧，因为不在堆顶，所以不会对当前的答案产生影响。所以就可以等到过期的区间到了堆顶，对当前答案产生影响了再删除也不迟。

二、天际线问题

class Solution {
public:

    typedef pair<int,int> pii;

    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        int n=buildings.size();    
    
        //因为区间有可能恰好重合，所以考虑将闭区间转化成左闭右开
        //考虑对每个区间记三个值[l,r-1,r]
        //对所有数去重排序进行离散化，用排名代替数值
        //之后根据开头位置从小到大排序，用大根堆维护大楼的高度

        vector<int>sorted(3*n+1);
        int sz=1;
        for(int i=0;i<n;i++)
        {
            sorted[sz++]=buildings[i][0];
            sorted[sz++]=buildings[i][1]-1;
            sorted[sz++]=buildings[i][1];
        }

        sort(sorted.begin()+1,sorted.end());

        //去重
        int len=1;
        for(int i=1;i<sz;i++)
        {
            if(sorted[len]!=sorted[i])
            {
                sorted[++len]=sorted[i];
            }
        }

        //修改左右边界
        for(int i=0;i<n;i++)
        {
            buildings[i][0]=rank(buildings[i][0],len,sorted);
            buildings[i][1]=rank(buildings[i][1]-1,len,sorted);
        }

        //左边界从小到大排序
        sort(buildings.begin(),buildings.end(),[](vector<int>&a,vector<int>&b)
        {
            return a[0]<b[0];
        });

        //高度
        vector<int>height(len+1);
        //大根堆维护高度
        priority_queue<pii>heap;

        for(int i=1,j=0;i<=len;i++)
        {
            //小于等于的入堆
            while(j<n&&buildings[j][0]<=i)
            {
                //{高度，右边界}
                heap.push({buildings[j][2],buildings[j][1]});
                j++;
            }

            //排除过期的数据
            while(!heap.empty()&&heap.top().second<i)
            {
                heap.pop();
            }

            if(!heap.empty())
            {
                height[i]=heap.top().first;
            }
        }

        vector<vector<int>>ans;
        for(int i=1,pre=0;i<=len;i++)
        {
            //去重
            if(pre!=height[i])
            {
                ans.push_back({sorted[i],height[i]});
            }
            pre=height[i];
        }

        return ans;
    }

    //查排名
    int rank(int v,int n,vector<int>&sorted)
    {
        int l=1;
        int r=n;
        int m;
        int ans=0;
        while(l<=r)
        {
            m=(l+r)>>1;

            if(sorted[m]<=v)
            {
                ans=m;
                l=m+1;
            }
            else
            {
                r=m-1;
            }
        }
        return ans;
    }
};

首先还是老套路，因为区间有可能重叠，所以考虑将闭区间转化为左闭右开区间。之后同样因为数轴的范围非常大，所以还要考虑对所有值进行离散化。离散化的方法是，对每个区间记三个值l,r-1和r，然后把所有点合起来进行离散化，然后转化原区间的左右边界为左闭右开，并修改为离散化后的排名。

之后，考虑先对左边界从小到大排序，然后用一个大根堆维护高度。之后用扫描线沿着数轴从左往右扫，还是每次让当前扫到的边界入堆，然后淘汰右边界过期的数据，并往高度数组里填入当前的最大值即可。所以最后，只需要再遍历一遍高度数组，对连续相等的高度进行去重即可。

三、扫描线 & 矩形面积并

思路太妙了！

对于这些矩形，首先考虑设置若干个事件，每个事件记录当前在横坐标x位置，在纵坐标的某个区间上出现了一条某个矩形的左边或右边，用+1或-1表示。举个例子，按横坐标从小到大对事件排序后就是如上图所示。

有了这几个事件，那么就可以用扫描线从左往右扫，每次结算当前产生的面积即可。这里首先先默认存在一个结构，可以维护纵坐标上出现的区间的总长度。那么首先第一个事件到来，就在10位置存在了一条[10,40]的边。然后当第二个事件来时，就在30位置存在了一条[50,70]的边。此时，由于到了30位置，那么第一个事件形成的边就可以产生面积的贡献，即产生(30-10)*(40-10)的贡献。注意当第四个事件来时，纵坐标上覆盖的长度为60，并非单纯增加。按照这个方法，遍历完所有事件，就可以统计出所有矩形的面积并。

那么之后就需要考虑如何建立一个结构，去维护纵坐标上出现的区间的长度。

这里，首先收集每个矩形上下边界的纵坐标并排序，然后把最大值重复收集一遍。之后考虑用线段树维护三个信息，分别是区间总长度，区间覆盖长度和区间整体被完全覆盖的次数。那么此时1~8范围上负责的区域，就是8再加1的负责的位置3100，减去1对应的位置100，所以长度为3000。

当第一个事件来时，这个区间根据左侧的表可以查到是[3,5]范围，这里注意要向下取。所以在下发时，当下发到[3,4]范围时，由于被全覆盖了，那么就把全覆盖次数+1，覆盖长度修改为700，然后往上汇总。类似地，当来到[5,5]范围时，还是由于被全覆盖了，所以对应修改然后返回即可。

当第二个事件来临时，整体过程和上述差不多，由于3000~3100只由7这个节点负责，那么就是直接暴力下扎到叶节点修改即可。

当第三个事件来时，因为负责的区间是[3,4]，所以在扎到[3,4]区间时直接修改，将全覆盖的次数加1即可。

当第四个事件来时，负责的区间是[1,4]，所以在扎到[1,4]区间时直接将全覆盖的次数加1，然后将覆盖长度改为区间长度即可。

当来到一个终止事件时，负责区间[3,4]，所以在扎到对应区间时直接让覆盖次数-1即可。这里注意，因为一个左边界必然对应一个右边界，且每次查询只查询整个范围上的长度，所以线段树不需要懒信息下发。

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;

const int MAXN=3e5+5;

//矩形坐标
vector<vector<int>>rec(MAXN,vector<int>(4));
//矩形两竖直边的事件
vector<vector<int>>line(MAXN,vector<int>(4));
//y值离散化
vector<int>ysort(MAXN);

//总长度
vector<int>length(MAXN<<2);
//覆盖长度
vector<int>cover(MAXN<<2);
//整体覆盖次数
vector<int>times(MAXN<<2);

void up(int i)
{
    //被全覆盖
    if(times[i]>0)
    {
        cover[i]=length[i];
    }
    //没被全覆盖
    else
    {
        cover[i]=cover[i<<1]+cover[i<<1|1];
    }
}

void add(int jobl,int jobr,int jobv,int l,int r,int i)
{
    if(jobl<=l&&r<=jobr)
    {
        //增加覆盖次数
        times[i]+=jobv;
    }
    else
    {
        int m=(l+r)>>1;

        if(jobl<=m)
        {
            add(jobl,jobr,jobv,l,m,i<<1);
        }
        if(m+1<=jobr)
        {
            add(jobl,jobr,jobv,m+1,r,i<<1|1);
        }
    }

    up(i);
}

void build(int l,int r,int i)
{
    if(l<r)
    {
        int m=(l+r)>>1;
        build(l,m,i<<1);
        build(m+1,r,i<<1|1);
    }
    length[i]=ysort[r+1]-ysort[l];
    times[i]=0;
    cover[i]=0;
}

int bs(int v,int n)
{
    int l=1;
    int r=n;
    int m;
    int ans=0;
    while(l<=r)
    {
        m=(l+r)>>1;

        if(ysort[m]>=v)
        {
            ans=m;
            r=m-1;
        }
        else
        {
            l=m+1;
        }
    }
    return ans;
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>rec[i][0]>>rec[i][1]>>rec[i][2]>>rec[i][3];
    }

    for(int i=1,j=1+n,x1,y1,x2,y2;i<=n;i++,j++)
    {
        x1=rec[i][0];
        y1=rec[i][1];
        x2=rec[i][2];
        y2=rec[i][3];

        //y值离散化
        ysort[i]=y1;
        ysort[j]=y2;

        //增加的事件
        line[i][0]=x1;
        line[i][1]=y1;
        line[i][2]=y2;
        line[i][3]=1;

        //减少的事件
        line[j][0]=x2;
        line[j][1]=y1;
        line[j][2]=y2;
        line[j][3]=-1;
    }

    //n扩一倍
    n<<=1;

    //排序去重
    sort(ysort.begin()+1,ysort.begin()+n+1);
    int m=1;
    for(int i=2;i<=n;i++)
    {
        if(ysort[m]!=ysort[i])
        {
            ysort[++m]=ysort[i];
        }
    }
    //补一个
    ysort[m+1]=ysort[m];

    build(1,m,1);

    //事件根据x值排序
    sort(line.begin()+1,line.begin()+1+n);

    ll ans=0;
    //扫描线
    for(int i=1,pre=0;i<=n;i++)
    {
        //cover[1]:y轴整个范围上的覆盖长度
        ans+=1ll*cover[1]*(line[i][0]-pre);
        
        pre=line[i][0];

        add(bs(line[i][1],m),bs(line[i][2],m)-1,line[i][3],1,m,1);
    }

    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();    
    }
    return 0;
}

大部分代码还是离散化和预处理的，记得最后再给y值表里多存一个。之后就是用扫描线从左往右扫，那么每次产生的贡献就是y轴整个范围上的覆盖长度，即cover[1]乘以x轴上的变化量，然后再更新线段树即可。

四、矩形周长 Picture

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;

const int MAXN=2e4+5;

//矩形坐标
vector<vector<int>>rec(MAXN,vector<int>(4));
//矩形两竖直边的事件
vector<vector<int>>line(MAXN,vector<int>(4));
//x和y值的离散化
vector<int>vsort(MAXN);

//总长度
vector<int>length(MAXN<<2);
//覆盖长度
vector<int>cover(MAXN<<2);
//整体覆盖次数
vector<int>times(MAXN<<2);

void up(int i)
{
    //被全覆盖
    if(times[i]>0)
    {
        cover[i]=length[i];
    }
    //没被全覆盖
    else
    {
        cover[i]=cover[i<<1]+cover[i<<1|1];
    }
}

void add(int jobl,int jobr,int jobv,int l,int r,int i)
{
    if(jobl<=l&&r<=jobr)
    {
        //增加覆盖次数
        times[i]+=jobv;
    }
    else
    {
        int m=(l+r)>>1;

        if(jobl<=m)
        {
            add(jobl,jobr,jobv,l,m,i<<1);
        }
        if(m+1<=jobr)
        {
            add(jobl,jobr,jobv,m+1,r,i<<1|1);
        }
    }

    up(i);
}

void build(int l,int r,int i)
{
    if(l<r)
    {
        int m=(l+r)>>1;
        build(l,m,i<<1);
        build(m+1,r,i<<1|1);
    }
    length[i]=vsort[r+1]-vsort[l];
    times[i]=0;
    cover[i]=0;
}

int bs(int v,int n)
{
    int l=1;
    int r=n;
    int m;
    int ans=0;
    while(l<=r)
    {
        m=(l+r)>>1;

        if(vsort[m]>=v)
        {
            ans=m;
            r=m-1;
        }
        else
        {
            l=m+1;
        }
    }
    return ans;
}

//排序去重
int prepare(int n)
{
    sort(vsort.begin()+1,vsort.begin()+n+1);
    int m=1;
    for(int i=2;i<=n;i++)
    {
        if(vsort[m]!=vsort[i])
        {
            vsort[++m]=vsort[i];
        }
    }
    //补一个
    vsort[m+1]=vsort[m];

    return m;
}

//扫描
ll scan(int n)
{
    int m=prepare(n);

    build(1,m,1);

    //事件从小到大排序
    sort(line.begin()+1,line.begin()+1+n,[](vector<int>&x,vector<int>&y)
    {
        return x[0]<y[0];
    });

    ll ans=0;
    //扫描线
    for(int i=1,pre=0;i<=n;i++)
    {
        pre=cover[1];

        //先施加影响
        add(bs(line[i][1],m),bs(line[i][2],m)-1,line[i][3],1,m,1);

        //cover[1]:整个范围上的覆盖长度
        ans+=1ll*abs(cover[1]-pre);
    }

    return ans;
}

//竖直扫
ll scanX(int n)
{
    for(int i=1,j=1+n,x1,y1,x2,y2;i<=n;i++,j++)
    {
        x1=rec[i][0];
        y1=rec[i][1];
        x2=rec[i][2];
        y2=rec[i][3];

        //X值离散化
        vsort[i]=x1;
        vsort[j]=x2;

        //增加的事件
        line[i][0]=y1;
        line[i][1]=x1;
        line[i][2]=x2;
        line[i][3]=1;

        //减少的事件
        line[j][0]=y2;
        line[j][1]=x1;
        line[j][2]=x2;
        line[j][3]=-1;
    }

    return scan(n<<1);
}

//水平扫
ll scanY(int n)
{
    for(int i=1,j=1+n,x1,y1,x2,y2;i<=n;i++,j++)
    {
        x1=rec[i][0];
        y1=rec[i][1];
        x2=rec[i][2];
        y2=rec[i][3];

        //y值离散化
        vsort[i]=y1;
        vsort[j]=y2;

        //增加的事件
        line[i][0]=x1;
        line[i][1]=y1;
        line[i][2]=y2;
        line[i][3]=1;

        //减少的事件
        line[j][0]=x2;
        line[j][1]=y1;
        line[j][2]=y2;
        line[j][3]=-1;
    }

    return scan(n<<1);
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>rec[i][0]>>rec[i][1]>>rec[i][2]>>rec[i][3];
    }

    cout<<scanX(n)+scanY(n)<<endl;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();    
    }
    return 0;
}

如果上个题明白了，这个题就很好懂了。因为上个题只考虑了在y方向上的边长，而这个题是统计周长，那么x方向和y方向上的边长就都要算，所以就可以用扫描线在x和y方向上都扫一次。此外，在这个题里，当每个事件来临时，由于这条边直接就会产生影响，所以需要先记录前一次整体的长度，再施加影响，最后才结算答案，统计当前和前一次长度的变化值。

总结

加快速度，加油！！

END