[数据结构与算法]线段树进阶（离散化与扫描线）

导语

在线段树的基本知识上进行拓展，学习一些进阶算法

离散化

以前也接触过这一知识点，准确来说，离散化属于一种思维或者方法，而不能特定的作用于某一类题目。离散化的具体意思就是把较大空间中有限的个体通过映射压缩到有限的空间中，提高算法的时空效率，当给出的数据量小而值大时，与其以绝对大小作为参照，不如用相对大小作为参照，以下标作为依据，这样可操作值域得以缩小，具体代码如下

代码

sort(b+1,b+1+n);
int tot=unique(b+1,b+1+n)-b-1;//去重
int pos=lower_bound(b+1,b+1+tot,a[i])-b;//a[i]的位置

扫描线

扫描线的应用基础如下：给出二维直角坐标系上若干个矩形的对角坐标，求出矩形相互覆盖后的面积

一般来说，求解时默认矩阵均在第一象限，如果不是，可以直接将坐标偏移后取离散化，当然也可以直接离散化，只是是否增加绝对值的问题，具体思路不多讲，可以参考后面的文献，只简单说一下思想：

1. 用平行与y轴的直线自左向右平移，分别与矩阵左边界右边界相遇
2. y轴上设置线段树记录区间覆盖长度
3. 遇到一边界时，计算面积，用下一边界减去当前边界，获矩形宽，取线段树区间覆盖长度获矩形长，遂得面积
4. 若为左边界，表对应区间覆盖数增，否则减
5. 以此往复

ps:感谢工程

代码（以LuoguP5490为例）

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,cnt,acc;
int py[maxn<<1];
struct node {
    int x,yy1,y2;
    int c;
    bool operator<(const node&p)const {
        if(x==p.x)return c>p.c;//增加在前，sort可能因为稳定性的问题会排序出错
        return x<p.x;
    }
} line[maxn<<2];
struct p {
    int cover;
    int sum;
} seg[maxn<<4];
void PushUp(int l,int r,int rt) {
    if(seg[rt].cover>0)seg[rt].sum=py[r]-py[l];//存在覆盖，即区间和
    else if(l+1==r)seg[rt].sum=0;//叶子节点
    else seg[rt].sum=seg[ls].sum+seg[rs].sum;//未覆盖使其代表有效和(左右区间有效值)
}
void Update(int L,int R,int l,int r,int rt,int c) {
    if(L>r||R<l)return ;
    if(L<=l&&R>=r) {
        seg[rt].cover+=c;
        PushUp(l,r,rt);
        return ;
    }
    if(l+1==r)return ;//到叶子节点，每个叶子节点实际上是一个区间
    int mid=(l+r)>>1;
    if(L<=mid)Update(L,R,l,mid,ls,c);
    if(R>mid)Update(L,R,mid,r,rs,c);//进入叶子节点，不是mid+1
    PushUp(l,r,rt);
}
void Build(int l,int r,int rt) {
    seg[rt].cover=0;
    seg[rt].sum=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    Build(l,mid,ls);
    Build(mid+1,r,rs);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n;
    for(int i=1; i<=n; i++) {
        int x,y,xx,yy;
        cin >>x>>y>>xx>>yy;
        line[++cnt]=(node) {//存矩阵左边界
            x,y,yy,1
        };
        py[cnt]=y;
        line[++cnt]=(node) {//存矩阵右边界
            xx,y,yy,-1
        };
        py[cnt]=yy;
    }
    sort(line+1,line+1+cnt);//排序便于离散化
    sort(py+1,py+1+cnt);//同上
    int len=unique(py+1,py+1+cnt)-py-1;
    int ans=0;
    //离散化
    Build(1,len,1);
    for(int i=1; i<cnt; i++) {
        int ll=lower_bound(py+1,py+1+len,line[i].yy1)-py;
        int rr=lower_bound(py+1,py+1+len,line[i].y2)-py;
        int c=line[i].c;
        Update(ll,rr,1,len,1,c);
        ans+=seg[1].sum*(line[i+1].x-line[i].x);//统计覆盖长度
    }
    cnt=0;
    cout <<ans;
    return 0;
}

训练

POJ2528

题目大意：略

思路：由于后面的海报一定会覆盖前面的海报，所以直接从后面的海报开始即可，每次标记已经贴了的区间，判断每次贴的区间是否有空

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e4+5;
int t,n,l[maxn],r[maxn],section[maxn<<2],cnt,res;
struct node {
    bool val;
} seg[maxn<<4];
void PushDown(int rt) {
    if(seg[rt].val) {
        seg[rt].val=0;
        seg[rt<<1].val=1;
        seg[rt<<1|1].val=1;
    }
}
bool Query(int L,int R,int l,int r,int rt) {
    if(L<=l&&r<=R)return seg[rt].val;
    int mid=(l+r)>>1;
    bool flag=1;
    PushDown(rt);
    if(L<=mid)
        flag&=Query(L,R,l,mid,rt<<1);
    if(R>mid)
        flag&=Query(L,R,mid+1,r,rt<<1|1);
    return flag;
}
void Update(int L,int R,int l,int r,int rt) {
    if(L<=l&&r<=R) {
        seg[rt].val=1;
        return ;
    }
    int mid=(l+r)>>1;
    PushDown(rt);
    if(L<=mid)
        Update(L,R,l,mid,rt<<1);
    if(R>mid)
        Update(L,R,mid+1,r,rt<<1|1);
    seg[rt].val=(seg[rt<<1].val&seg[rt<<1|1].val);
}
void Build(int l,int r,int rt) {
    if(l==r) {
        seg[rt].val=0;
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    seg[rt].val=(seg[rt<<1].val&seg[rt<<1|1].val);
}
int main() {
    scanf("%d",&t);
    while(t--) {
        cin >>n;
        cnt=0,res=0;
        for(int i=1; i<=n; i++) {//存下每个值准备离散化
            cin >>l[i]>>r[i];
            section[++cnt]=l[i];
            section[++cnt]=r[i];
        }
        Build(1,cnt+1,1);//初始化线段树，注意范围
        sort(section+1,section+1+cnt);//排序
        int len=unique(section+1,section+1+cnt)-section-1;//获得去重之后的长度
        for(int i=n; i>=1; i--) {
            int ll=lower_bound(section+1,section+1+len,l[i])-section;
            int rr=lower_bound(section+1,section+1+len,r[i])-section;
            if(!Query(ll,rr,1,len,1))res++;//判断区间是否有空
            Update(ll,rr,1,len,1);
        }
        cout <<res<<endl;
    }
    return 0;
}

POJ1151

题目大意：二维坐标系，仅第一象限，给出多个矩形左上点和右下点，求所有矩形面积并

思路：扫描线模板题，但是数据为小数，需要用double来存储

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;
const int maxn=1e4+5;
int n,cnt,acc;
double py[maxn<<1];
struct node {
    double x,yy1,y2;
    int c;
    bool operator<(const node&p)const {
        if(x==p.x)return c>p.c;//增加在前，sort可能因为稳定性的问题会排序出错
        return x<p.x;
    }
} line[maxn<<1];
struct p {
    int cover;
    double sum;
} seg[maxn<<2];
void PushUp(int l,int r,int rt) {
    if(seg[rt].cover>0)seg[rt].sum=py[r]-py[l];//存在覆盖，即区间和
    else if(l+1==r)seg[rt].sum=0;//叶子节点
    else seg[rt].sum=seg[ls].sum+seg[rs].sum;//未覆盖使其代表有效和(左右区间有效值)
}
void Update(int L,int R,int l,int r,int rt,int c) {
    if(L>r||R<l)return ;
    if(L<=l&&R>=r) {
        seg[rt].cover+=c;
        PushUp(l,r,rt);
        return ;
    }
    if(l+1==r)return ;//到叶子节点，每个叶子节点实际上是一个区间
    int mid=(l+r)>>1;
    if(L<=mid)Update(L,R,l,mid,ls,c);
    if(R>mid)Update(L,R,mid,r,rs,c);//进入叶子节点，不是mid+1
    PushUp(l,r,rt);
}
void Build(int l,int r,int rt) {
    seg[rt].cover=0;
    seg[rt].sum=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    Build(l,mid,ls);
    Build(mid+1,r,rs);
}
int main() {
    while(~scanf("%d",&n)&&n) {
        acc++;
        for(int i=1; i<=n; i++) {
            double x,y,xx,yy;
            scanf("%lf%lf%lf%lf",&x,&y,&xx,&yy);
            line[++cnt]=(node) {//存矩阵左边界
                x,y,yy,1
            };
            py[cnt]=y;
            line[++cnt]=(node) {//存矩阵右边界
                xx,y,yy,-1
            };
            py[cnt]=yy;
        }
        sort(line+1,line+1+cnt);//排序便于离散化
        sort(py+1,py+1+cnt);//同上
        int len=unique(py+1,py+1+cnt)-py-1;
        double ans=0;
        //离散化
        Build(1,len,1);
        for(int i=1; i<cnt; i++) {
            int ll=lower_bound(py+1,py+1+len,line[i].yy1)-py;
            int rr=lower_bound(py+1,py+1+len,line[i].y2)-py;
            int c=line[i].c;
            Update(ll,rr,1,len,1,c);
            ans+=seg[1].sum*(line[i+1].x-line[i].x);//统计覆盖长度
        }
        cnt=0;
        printf("Test case #%d\n",acc);
        printf("Total explored area: %.2f\n\n",ans);
    }
    return 0;
}

POJ1177

题目大意：二维坐标系，给出多个矩形左上点和右下点，求所有矩形构成的整体图形的周长

思路：求周长并模板题，只需要横竖都进行一次扫描线即可

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls (rt<<1)
#define rs (rt<<1|1)
//#define int long long
using namespace std;
const int maxn=1e4+5;
int n,cnt,acc;
int py[maxn<<1],px[maxn<<1];
struct node {
    int x,yy1,y2;
    int c;
    bool operator<(const node&p)const {
        if(x==p.x)return c>p.c;//增加在前，sort可能因为稳定性的问题会排序出错
        return x<p.x;
    }
} linex[maxn<<2],liney[maxn<<1];
struct p {
    int cover;
    int sum;
} seg[maxn<<4];
void PushUp(int l,int r,int rt,bool f) {
    if(seg[rt].cover>0)f?seg[rt].sum=py[r]-py[l]:seg[rt].sum=px[r]-px[l];//存在覆盖，即区间和
    else if(l+1==r)seg[rt].sum=0;//叶子节点
    else seg[rt].sum=seg[ls].sum+seg[rs].sum;//未覆盖使其代表有效和(左右区间有效值)
}
void Update(int L,int R,int l,int r,int rt,int c,bool f) {
    if(L>r||R<l)return ;
    if(L<=l&&R>=r) {
        seg[rt].cover+=c;
        PushUp(l,r,rt,f);
        return ;
    }
    if(l+1==r)return ;//到叶子节点，每个叶子节点实际上是一个区间
    int mid=(l+r)>>1;
    if(L<=mid)Update(L,R,l,mid,ls,c,f);
    if(R>mid)Update(L,R,mid,r,rs,c,f);//进入叶子节点，不是mid+1
    PushUp(l,r,rt,f);
}
void Build(int l,int r,int rt) {
    seg[rt].cover=0;
    seg[rt].sum=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    Build(l,mid,ls);
    Build(mid+1,r,rs);
}
signed main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        int x,y,xx,yy;
        scanf("%d%d%d%d",&x,&y,&xx,&yy);
        x+=maxn,y+=maxn,xx+=maxn,yy+=maxn;//可加可不加
        linex[++cnt]= {x,y,yy,1};
        py[cnt]=y;
        linex[++cnt]= {xx,y,yy,-1};
        py[cnt]=yy;
        liney[++acc]= {y,x,xx,1};
        px[acc]=x;
        liney[++acc]= {yy,x,xx,-1};
        px[acc]=xx;
    }
    sort(linex+1,linex+1+cnt);
    sort(liney+1,liney+1+acc);
    sort(py+1,py+1+cnt);
    sort(px+1,px+1+acc);
    int lenx=unique(py+1,py+1+cnt)-py-1;
    int leny=unique(px+1,px+1+acc)-px-1;
    int ans=0,last=0;
    Build(1,cnt,1);
    for(int i=1; i<=cnt; i++) {
        int ll=lower_bound(py+1,py+1+lenx,linex[i].yy1)-py;
        int rr=lower_bound(py+1,py+1+lenx,linex[i].y2)-py;
        int c=linex[i].c;
        //if(ll>rr)swap(ll,rr);
        Update(ll,rr,1,lenx,1,c,1);
        ans+=abs(seg[1].sum-last);
        last=seg[1].sum;
    }
    Build(1,cnt,1);
    last=0;
    for(int i=1; i<=acc; i++) {
        int ll=lower_bound(px+1,px+1+leny,liney[i].yy1)-px;
        int rr=lower_bound(px+1,px+1+leny,liney[i].y2)-px;
        int c=liney[i].c;
        //if(ll>rr)swap(ll,rr);
        Update(ll,rr,1,leny,1,c,0);
        ans+=abs(seg[1].sum-last);
        last=seg[1].sum;
    }
    printf("%d",ans);
    return 0;
}

POJ2482

题目大意：给出二维直角坐标系，坐标系中存在多个整点，每个点有点权，给出一个宽w，高h的矩形，询问矩形能够圈出的最大点权和（边界不算）

思路：只有一个矩形，且矩形的大小固定，那么矩形可以由唯一顶点确定，以右上点为基准，考虑矩形的摆放位置，设一个给定的点坐标为$(x,y)$，点权为$c$，如果想要圈住这一点，右上点的坐标范围可根据题目条件推得$(x,y)??(x+w?1,y+h?1)$，那么问题转换成，平面上有若干矩形区域，每个区域有权值，求在哪个坐标上重叠的区域权值和最大，因此可以用扫描线更新记录覆盖的权值，详见代码

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,cnt,acc,w,h;
int py[maxn<<1];
struct node {
    int x,yy1,y2;
    int c;
    bool operator<(const node&p)const {
        if(x==p.x)return c>p.c;//增加在前，sort可能因为稳定性的问题会排序出错
        return x<p.x;
    }
} line[maxn<<2];
struct p {
    int cover;//区间权值和最值
    int sum;//权值和标记
} seg[maxn<<4];
void PushUp(int rt) {
    seg[rt].cover=max(seg[rt<<1].cover,seg[rt<<1|1].cover);//更新最大权值和
}
void PushDown(int rt) {
    seg[ls].cover+=seg[rt].sum;//最值都累和
    seg[rs].cover+=seg[rt].sum;
    seg[ls].sum+=seg[rt].sum;//标记累和
    seg[rs].sum+=seg[rt].sum;
    seg[rt].sum=0;
}
void Update(int L,int R,int l,int r,int rt,int c) {
    if(L>r||R<l)return ;
    if(L<=l&&R>=r) {
        seg[rt].cover+=c;
        seg[rt].sum+=c;
        return ;
    }
    if(l==r)return ;
    PushDown(rt);
    int mid=(l+r)>>1;
    if(L<=mid)Update(L,R,l,mid,ls,c);
    if(R>mid)Update(L,R,mid+1,r,rs,c);
    //这个地方就可以用点了，因为不是区间，是判断点是否覆盖
    PushUp(rt);
}
void Build(int l,int r,int rt) {
    seg[rt].cover=0;
    seg[rt].sum=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    Build(l,mid,ls);
    Build(mid+1,r,rs);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin >>n>>w>>h) {
        for(int i=1; i<=n; i++) {
            int x,y,c,xx,yy;
            cin >>x>>y>>c;
            xx=x+w-1;
            yy=y+h-1;
            line[++cnt]=(node) {//存矩阵左边界
                x,y,yy,c
            };
            py[cnt]=y;
            line[++cnt]=(node) {//存矩阵右边界
                xx,y,yy,-c
            };
            py[cnt]=yy;
        }
        sort(line+1,line+1+cnt);//排序便于离散化
        sort(py+1,py+1+cnt);//同上
        int len=unique(py+1,py+1+cnt)-py-1;
        int ans=0;
        //离散化
        Build(1,len,1);
        for(int i=1; i<cnt; i++) {
            int ll=lower_bound(py+1,py+1+len,line[i].yy1)-py;
            int rr=lower_bound(py+1,py+1+len,line[i].y2)-py;
            int c=line[i].c;
            Update(ll,rr,1,len,1,c);
            ans=max(seg[1].cover,ans);//取累和权值最大值
        }
        cnt=0;
        cout <<ans<<endl;
    }
    return 0;
}

CF817F

题目大意：略

思路：题目的翻译有点问题，应该是当前存在与集合中的数和不存在于集合中的数，而不是存在过的数
由于数值很大，故离散化处理，线段树节点分别存区间内存在于集合中个数，翻转标记，加/删标记，由于是输出在集合中没有出现过的最小正整数，需要考虑输入数据之外的边界，如1和$max(r_i)+1$，其余详见代码

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int n,num[maxn<<1],cnt;
struct p {
    int t,l,r;
} op[maxn];
struct node {
    int val;
    int xr,tag;
} seg[maxn<<4];
void PushDown(int l,int r,int rt) {
    int mid=(l+r)>>1;
    if(seg[rt].tag!=-1) {//删除或添加
        seg[rt<<1|1].tag=seg[rt<<1].tag=seg[rt].tag;//继承标记
        seg[rt<<1].xr=seg[rt<<1|1].xr=0;//清空，tag优先级更高
        if(seg[rt].tag) {//执行对应操作
            seg[rt<<1].val=mid-l+1;
            seg[rt<<1|1].val=r-mid;
        } else
            seg[rt<<1].val=seg[rt<<1|1].val=0;
        seg[rt].tag=-1;
    }
    if(seg[rt].xr) {//存在翻转
        if(seg[rt<<1].tag!=-1)seg[rt<<1].tag^=1;//tag存在，直接翻转tag即可
        else seg[rt<<1].xr^=1;//否则翻转标记
        if(seg[rt<<1|1].tag!=-1)seg[rt<<1|1].tag^=1;
        else seg[rt<<1|1].xr^=1;
        seg[rt<<1].val=mid-l+1-seg[rt<<1].val;//翻转变值
        seg[rt<<1|1].val=r-mid-seg[rt<<1|1].val;
        seg[rt].xr=0;
    }
}
void PushUp(int rt) {
    seg[rt].val=seg[rt<<1].val+seg[rt<<1|1].val;//区间和
}
int Query(int l,int r,int rt) {//单点查询
    if(l==r)return l;
    PushDown(l,r,rt);
    int mid=(l+r)>>1;
    if(seg[rt<<1].val<mid-l+1)return Query(l,mid,rt<<1);//区间未满，存在解
    return Query(mid+1,r,rt<<1|1);
}
void Update(int t,int L,int R,int l,int r,int rt) {
    if(L<=l&&r<=R) {
        if(l==r) {
            if(t==1)seg[rt].val=1;
            else if(t==2)seg[rt].val=0;
            else seg[rt].val^=1;
        } else {
            switch(t) {
            case 1:
                seg[rt].val=r-l+1;
                seg[rt].tag=1;
                seg[rt].xr=0;
                break;
            case 2:
                seg[rt].val=0;
                seg[rt].tag=0;
                seg[rt].xr=0;
                break;
            case 3:
                if(seg[rt].tag!=-1)seg[rt].tag^=1;//翻转只需翻转tag
                else seg[rt].xr^=1;//否则翻转标记
                seg[rt].val=r-l+1-seg[rt].val;
                break;
            }
        }
        return ;
    }
    PushDown(l,r,rt);
    int mid=(l+r)>>1;
    if(L<=mid)Update(t,L,R,l,mid,rt<<1);
    if(mid<R)Update(t,L,R,mid+1,r,rt<<1|1);
    PushUp(rt);
}
void Build(int l,int r,int rt) {
    seg[rt].val=seg[rt].xr=0;
    seg[rt].tag=-1;
    if(l==r)return ;
    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    PushUp(rt);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n;
    num[++cnt]=1;//非常重要，因为操作区间内可能没有1，但是1满足条件
    for(int i=1; i<=n; i++) {
        cin >>op[i].t>>op[i].l>>op[i].r;
        num[++cnt]=op[i].l;
        num[++cnt]=op[i].r;
        num[++cnt]=op[i].r+1;//非常重要，可能1到r都满，只有r+1满足条件
    }
    sort(num+1,num+1+cnt);
    int len=unique(num+1,num+1+cnt)-num-1;//离散化
    Build(1,len,1);
    for(int i=1; i<=n; i++) {
        int l=lower_bound(num+1,num+1+len,op[i].l)-num;
        int r=lower_bound(num+1,num+1+len,op[i].r)-num;
        Update(op[i].t,l,r,1,len,1);
        cout <<num[Query(1,len,1)]<<endl;
    }
    return 0;
}

CF377D

题目大意：略

思路：详见工程博客，讲的很清晰了

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,cnt,acc,ll[maxn],vv[maxn],rr[maxn];
int py[maxn<<1],pos[maxn<<3];
struct node {
    int x,yy1,y2;
    int c;
    bool operator<(const node&p)const {
        if(x==p.x)return c>p.c;//增加在前，sort可能因为稳定性的问题会排序出错
        return x<p.x;
    }
} line[maxn<<2];
struct p {
    int cover;//区间覆盖次数
    int sum;//标记
} seg[maxn<<4];
void PushUp(int rt) {
    if(seg[ls].cover>seg[rs].cover) {//取最多的覆盖次数
        seg[rt].cover=seg[ls].cover;
        pos[rt]=pos[ls];//记录最多覆盖次数存在的区间
    } else {
        seg[rt].cover=seg[rs].cover;
        pos[rt]=pos[rs];
    }
}
void PushDown(int rt) {
    seg[ls].cover+=seg[rt].sum;
    seg[rs].cover+=seg[rt].sum;
    seg[ls].sum+=seg[rt].sum;
    seg[rs].sum+=seg[rt].sum;
    seg[rt].sum=0;
}
void Update(int L,int R,int l,int r,int rt,int c) {
    if(L<=l&&R>=r) {
        seg[rt].cover+=c;
        seg[rt].sum+=c;
        return ;
    }
    if(l==r)return ;
    int mid=(l+r)>>1;
    PushDown(rt);
    if(L<=mid)Update(L,R,l,mid,ls,c);
    if(R>mid)Update(L,R,mid+1,r,rs,c);
    PushUp(rt);
}
void Build(int l,int r,int rt) {
    if(l==r) {
        pos[rt]=l;//赋初始值
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,ls);
    Build(mid+1,r,rs);
    pos[rt]=pos[rt<<1];//初始化位置，默认为左区间
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n;
    for(int i=1; i<=n; i++) {
        int l,v,r;
        cin >>l>>v>>r;
        ll[i]=l,vv[i]=v,rr[i]=r;
        line[++cnt]=(node) {//存矩阵左边界
            l,v,r,1
        };
        py[cnt]=v;
        line[++cnt]=(node) {//存矩阵右边界
            v,v,r,-1
        };
        py[cnt]=r;
    }
    sort(line+1,line+1+cnt);//排序便于离散化
    sort(py+1,py+1+cnt);//同上
    int len=unique(py+1,py+1+cnt)-py-1;
    int ans=0,L=0,R=0;
    //离散化
    Build(1,len,1);
    for(int i=1; i<=cnt; i++) {
        int lt=lower_bound(py+1,py+1+len,line[i].yy1)-py;
        int rt=lower_bound(py+1,py+1+len,line[i].y2)-py;
        int c=line[i].c;
        Update(lt,rt,1,len,1,c);
        if(ans<seg[1].cover) {
            ans=seg[1].cover;
            L=line[i].x;//最小值
            R=pos[1];//最大值
        }
    }
    cout <<ans<<endl;
    for(int i=1; i<=n; i++)
        if(ll[i]<=L&&L<=vv[i]&&vv[i]<=py[R]&&py[R]<=rr[i])
            cout <<i<<" ";
    return 0;
}

总结

扫描线问题，关键在于如何将条件转换成求二维坐标系上的矩形以及判断叶子节点是代表区间还是代表端点，对于不同的题，扫描线所构造出来的线段树有所不同，线段树的维护有所不同，但大多都与覆盖有关

参考文献

1. 西北工业大学ACM2017暑假集训-线段树进阶
2. 线段树总结
3. 【AgOHの算法胡扯】扫描线算法
4. P5490 【模板】扫描线 题解
5. 工程的博客
6. The 2021 ICPC Asia Taipei Regional F. What a Colorful Wall 扫描线 + 并查集

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生