线段树进阶运用

Nemonade · 2023-07-12 10:28:19 · 个人记录

【例题】扫描线

给出平面直角坐标系上的 n 个矩形，求这些矩形的面积并。

这实际上是一个计算几何的问题，可以使用线段树解决（据说线段树就是起源于计算几何的一维统计问题）。

样例如下：

好像容斥原理就可以了……吗？样例很简单，如果矩形很多，那么重叠部分的计算无法想象。所以维护重叠的思路时不行的。

那怎么办？同样考虑重叠部分，发现这部分是由那些矩形重叠、如何重叠并不重要，本质上都只计算一次，可以看作单独的一块（而不是其他矩形的一部分）来处理。

做辅助线：

划分成长方形：

那么这几个矩形的面积就稍微好求一点了。面积等于底乘高，总面积直接求和就可以了。再简化一下，把所有的矩形的上下两条线段拆下来，那么就可以保存这个矩形的所有信息。

如何计算高？直接把拆下来的所有线段按 y 值排序，然后从上到下考虑每一个矩形，高就很好求了。如何计算底长？显然的做法是从上往下的过程中开一个数组记录某个点被几个线段包含，然后底就是数组中非 0 数的个数。

整个过程是：把每个矩形拆成上下两个线段；按照 y 值排序；从上到下依次扫描所有线段，更改值域上的数组，求和，计算当前矩形的面积并累加答案。

像这样依次加入四条线段，面积分别加上了蓝色、红色、绿色的部分，最后算出总面积。当然，x 值需要离散化。复杂度 O(n^2)。

（动图自行倒过来看好吧）

再考虑优化。我们需要在每次遇到新线段的时候在经过离散化的 x 值上进行：区间加，询问有多少个非 0 点。而这个东西可以用线段树很方便地维护。于是复杂度优化为 O(n\log n)。

代码：

const int N=1e6+5;
int n,x,xx,y,yy,X[N],a[N],cnt,maxn=INT_MAX,ans;
struct SegmentTree{int l,r,cnt,len;}t[N<<2];
struct Line{int x,y,yy,mark;}line[N<<2];
inline void pushup(int p){
    if((t[p].l==maxn&&t[p].r==maxn)) return;
    if(t[p].cnt) t[p].len=a[t[p].r+1]-a[t[p].l];
    else t[p].len=t[p<<1].len+t[p<<1|1].len;
    return;
}
inline void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r) return;
    int mid=(t[p].l+t[p].r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    return;
}
inline void add(int p,int l,int r,int q){
    if(l<=t[p].l&&t[p].r<=r){t[p].cnt+=q;pushup(p);return;}
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) add(p<<1,l,r,q);
    if(mid<r) add(p<<1|1,l,r,q);
    pushup(p);
    return;
}
inline bool operator <(Line a, Line b){
    if(a.x!=b.x) return a.x<b.x;
    return a.mark>b.mark;
}
signed main(){
    n=read();
    pfor(i,1,n){
        x=read(),y=read(),xx=read(),yy=read();
        line[(i<<1)-1].x=x,line[i<<1].x=xx;
        line[(i<<1)-1].y=line[i<<1].y=yy;
        line[(i<<1)-1].yy=line[i<<1].yy=y;
        line[(i<<1)-1].mark=1,line[i<<1].mark=-1;
        X[++cnt]=y,X[++cnt]=yy;
    }
    sort(X+1,X+(n<<1)+1);
    cnt=unique(X+1,X+(n<<1)+1)-X-1;
    pfor(i,1,(n<<1)){
        int p1=lower_bound(X+1,X+cnt+1,line[i].y)-X;
        int p2=lower_bound(X+1,X+cnt+1,line[i].yy)-X;
        a[p1]=line[i].y,a[p2]=line[i].yy;
        line[i].y=p1,line[i].yy=p2;
        maxn=maxx(maxn,p1);
    }
    sort(line+1,line+(n<<1)+1);
    build(1,1,n<<1);
    pfor(i,1,(n<<1)){
        add(1,line[i].yy,line[i].y-1,line[i].mark);
        ans+=t[1].len*(line[i+1].x-line[i].x);
    }
    write(ans);
    return 0;
}

例题：

P3353 在你窗外闪耀的星星

P1856 [IOI1998] [USACO5.5] 矩形周长Picture

【例题】可持久化线段树 1（可持久化数组）

给出一个长度为 n 的序列 a，进行 m 次操作：

• 将某个历史版本中把某个点加上 x；

• 求某个历史版本中某个点的值。

既然要再历史版本上进行操作，显然可以每次都复制一份数组，但是时空都完全爆炸。

想到只能单 \log 的时空限制，考虑一些高级数据结构。树状数组拓展性差显然不行，平衡树不符合题目颜色也不行，那就只有线段树了。

查询变成了 O(\log n)，修改依然需要复制线段树，爆炸，如何优化？

我们再仔细考虑一下线段树单点修改的过程：从上到下依次修改 O(\log n) 个节点。所以一共 O(n) 个节点只有一小部分需要修改却要复制一份，造成了时空的浪费。

那咋办？它没改就不复制，直接用啊！

我们直接修改都新建一个树根然后把没有变的节点给连上去，变了的节点就新开，就是可持久化动态开点线段树（其实还不能叫主席树）。

盗图不过分吧。

int n,a[N],totp,root[N],opt,v,x,y;
struct SegmentTree{int l,r,lch,rch,data;}t[N<<2];
inline int New(int p){t[++totp]=t[p];return totp;}
inline int build(int l,int r){
    int p=++totp;t[p].l=l,t[p].r=r;
    if(l==r){t[p].data=a[l];return p;}
    int mid=(l+r)>>1;
    t[p].lch=build(l,mid);
    t[p].rch=build(mid+1,r);
    return p;
}
inline int change(int p,int x,int q){
    int np=New(p);
    if(t[p].l==t[p].r){t[np].data=q;return np;}
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid) t[np].lch=change(t[p].lch,x,q);
    if(x>mid) t[np].rch=change(t[p].rch,x,q);
    return np;
}
inline int ask(int p,int x){
    if(t[p].l==t[p].r) return t[p].data;
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid) return ask(t[p].lch,x);
    if(x>mid) return ask(t[p].rch,x);
}
signed main(){
    n=read();int kkk=read();
    pfor(i,1,n) a[i]=read();
    root[0]=build(1,n);
    pfor(i,1,kkk){
        v=read(),opt=read();
        if(opt==1){
            x=read(),y=read();
            root[i]=change(root[v],x,y);
        }
        else{
            x=read();
            write(ask(root[v],x)),puts("");
            root[i]=root[v];
        }
    }
    return 0;
}

【例题】可持久化线段树 2

给出一个长度为 n 的序列 a，进行 m 次操作：

• 求区间 [l,r] 中的第 k 小值。

维护值域的可持久化线段树，又叫主席树。

用主席树依次加入每一个值，得到一个有 O(n\log n) 个节点，n 个根的树。然后对于每个询问 [l,r]，把第 l-1 和第 r 棵树取出来。会发生什么？

我们发现两棵线段树对应节点 [x,y] 的数值相减就是 [l,r] 内在 [x,y] 之间的数的个数。所以说在这两棵树上进行类似平衡树查 kth 的操作就可以了。

具体来说，如果走到一个节点 [l,r]，在 [x,y] 内有 d 个数。那么如果 d<k 就往左递归，k 不变。否则，递归右子树，k\leftarrow k-d。

将序列 [1,1,4,5,1,4] 插入主席树的情况：

可以看到非常的抽象。

注意离散化。代码：

int n,m,a[N],b[N],c[N];
struct SegmentTree{
    int root[N],data[N*30],lch[N*40],rch[N*30],tot;
    inline void build(int& p,int l,int r){
        p=++tot;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(lch[p],l,mid),build(rch[p],mid+1,r);
        return;
    }
    inline int add(int p,int l,int r,int x){
        int q=++tot;
        data[q]=data[p]+1,lch[q]=lch[p],rch[q]=rch[p];
        if(l==r) return q;
        int mid=(l+r)>>1;
        if(x<=mid) lch[q]=add(lch[q],l,mid,x);
        else rch[q]=add(rch[q],mid+1,r,x);
        return q;
    }
    inline int query(int p,int q,int l,int r,int k){
        if(l==r) return l;
        int mid=(l+r)>>1;
        if(data[lch[q]]-data[lch[p]]>=k)
            return query(lch[p],lch[q],l,mid,k);
        else return query(rch[p],rch[q],mid+1,r,k+data[lch[p]]-data[lch[q]]);
    }
}T;
signed main(){
    n=rd();int kkk=rd();
    pfor(i,1,n) a[i]=b[i]=rd();
    sort(b+1,b+n+1);
    m=std::unique(b+1,b+n+1)-b-1;
    T.build(T.root[0],1,m);
    pfor(i,1,n){
        T.root[i]=T.add(T.root[i-1],1,m,std::lower_bound(b+1,b+m+1,a[i])-b);
    }
    while(kkk--){
        int x=rd(),y=rd(),k=rd();
        write(b[T.query(T.root[x-1],T.root[y],1,m,k)]),puts("");
    }
    return 0;
}

【例题】Dynamic Rankings

给出一个长度为 n 的序列 a，进行 m 次操作：

• 求区间 [l,r] 中的第 k 小值；

• 修改 x 的值。

树套树入门题。

我们重新思考一下用主席树查询静态区间 kth 的过程：不断比较两个版本的主席树在区间内数的个数的值，与 k 比较，往左或者右子树进行递归。这不就是前缀和吗？

而前缀和、单点修改，能想到什么？显然的树状数组。

于是直接在主席树外层套一个树状数组，这样就实现了 O(\log^2n) 的单次操作。

代码比较恶心人：

const int N=1e5+5;
int n,m,a[N],b[N<<1],tot,cnt[2],tmp[2][20];
struct PersistentSegmentTreeNode{int lch,rch,data;};
struct Questions{char opt;int x,y,z;}q[N];
struct PersistentSegmentTree{
    int root[N],tot;
    PersistentSegmentTreeNode t[N*400];
    inline void change(int &p,int l,int r,int x,int y){
        if(!p) p=++tot;
        t[p].data+=y;
        if(l==r) return;
        int mid=(l+r)>>1;
        if(x<=mid) change(t[p].lch,l,mid,x,y);
        else change(t[p].rch,mid+1,r,x,y);
        return;
    }
    inline int query(int l,int r,int k){
        if(l==r) return l;
        int mid=(l+r)>>1,res=0;
        pfor(i,1,cnt[0]) res-=t[t[tmp[0][i]].lch].data;
        pfor(i,1,cnt[1]) res+=t[t[tmp[1][i]].lch].data;
        if(k<=res){
            pfor(i,1,cnt[0]) tmp[0][i]=t[tmp[0][i]].lch;
            pfor(i,1,cnt[1]) tmp[1][i]=t[tmp[1][i]].lch;
            return query(l,mid,k);
        }
        pfor(i,1,cnt[0]) tmp[0][i]=t[tmp[0][i]].rch;
        pfor(i,1,cnt[1]) tmp[1][i]=t[tmp[1][i]].rch;
        return query(mid+1,r,k-res);
    }
}seg;
struct BinaryIndexTree{
    inline int lowbit(int x){return x&(-x);}
    inline void change(int x,int y){
        int k=std::lower_bound(b+1,b+tot+1,a[x])-b;
        for(int i=x;i<=n;i+=lowbit(i)) seg.change(seg.root[i],1,tot,k,y);
        return;
    }
    inline int query(int l,int r,int k){
        memset(tmp,0,sizeof tmp);
        cnt[0]=cnt[1]=0;
        for(int i=l-1;i;i-=lowbit(i)) tmp[0][++cnt[0]]=seg.root[i];
        for(int i=r;i;i-=lowbit(i)) tmp[1][++cnt[1]]=seg.root[i];
        return seg.query(1,tot,k);
    }
}tr;
signed main(){
    n=rd();int kkk=rd();
    pfor(i,1,n) a[i]=b[++tot]=rd();
    pfor(i,1,kkk){
        cin>>q[i].opt;
        if(q[i].opt=='Q') q[i].x=rd(),q[i].y=rd(),q[i].z=rd();
        else q[i].x=rd(),q[i].y=b[++tot]=rd();
    }
    sort(b+1,b+tot+1);
    tot=std::unique(b+1,b+tot+1)-b-1;
    pfor(i,1,n) tr.change(i,1);
    pfor(i,1,kkk){
        if(q[i].opt=='Q') write(b[tr.query(q[i].x,q[i].y,q[i].z)]),puts("");
        else{
            tr.change(q[i].x,-1);
            a[q[i].x]=q[i].y;
            tr.change(q[i].x,1);
        }
    }
    return 0;
}

例题：

P3157 [CQOI2011] 动态逆序对