题解：P11307 [COTS 2016] 建造费 Pristojba

TLEWA · 2025-01-18 00:22:52 · 题解

题解区怎么全部都是 O(n \log^{2} n) 的做法，赶快来发篇常数巨大的严格 O(n \log n) 题解！（认为 n,m 同阶）

解题思路

考虑优化朴素的最小生成树过程，由区间连边不难想到线段树优化建图，但是仔细思考之后会发现无法构造出合适的连边方式（也有可能是我太弱了），不过感觉线段树优化是一个感觉很正确的方向，于是我们遍历一下常用的最小生成树算法，发现 Prim 算法的流程似乎很容易转化成区间 RMQ 问题，考虑线段树优化 Prim。

考虑 Prim 算法的单轮流程，假设我们已经有了一个加入生成树中的点集 U，如何找到一个距离最近且不在点集中的点？从 U 出发的区间连边非常好在线段树上处理，直接使用类似标记永久化的技巧把最优的起点挂载在线段树节点上，在 pushup 时处理路径即可。但是如果区间连边的起点不在点集 U 中，在线段树上无法形成一个连续区间，难以处理。

怎么办？我们不妨利用 Prim 连边的对称性，取 U 的补集 V，也采用和维护 U 类似的方法建立一颗线段树，在这颗新树上，之前难以处理的连边情况变成了多段连续区间，也可以采用和 U 一样的方法维护了。

整理一下，现在我们需要实现两个数据结构：

维护点集 U 联向 V 的路径，支持以下操作：

往点集中加入一个点并断开原点集与其的所有连边
查询与点集 V 的最短连边

维护点集 V 联向 U 的路径，支持以下操作：

往点集中删除一个点，连接原点集与其的所有连边
查询与点集 U 的最短连边

最短连边使用前文所述的方法维护，往点集中加点的操作可以直接在挂载时与原最优起点取较小值，如何处理删点？不难想到可以直接使用 std::set 暴力维护，直接这样做的复杂度是 O(n \log^{2} n) 的，有没有更好的方法？

是有的，直接在有序序列上在线随机删除的复杂度不太可能低于 O(\log n)，但是我们可以把删除操作懒惰化。具体地，当我们从点集中删除一个点的时候，我们先标记一下这个点已经被删除，然后找到这个点连接的所有区间在线段树上对应的点，如果被删除的点是当前节点对应的最优起点，那么我们从起点队列中弹出这个起点，找到第一个未被删除的起点作为新起点，由于一个区间最多对应 \log n 个线段树节点，这么做的复杂度上界为 O(n \log n + m \log n)。

剩下就是如何初始化每个节点上的最优起点队列了，如果我们直接把起点下传到连边区间对应节点上进行排序，那么这部分复杂度会退化到最坏 O(n \log^{2} n)，不能接受。于是我们直接把 V 中所有起点先排序好，然后从根节点倒着做归并排序的流程就好了，这部分复杂度 O(n \log n)。

如果还有没解释清楚的地方，看代码吧。

AC 代码

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=100005,INF=1e9;

/*
常数起飞了/ll 
*/

int n,m;
int p[N];bool vis[N];

struct Node {int p,l,r;};

#define mid (tre[now].l+tre[now].r>>1)
#define lson (now*2)
#define rson (now*2+1)

struct Tre {
    int l,r;
    int min,min_cost; // 最小 p_i 和最小花费 
    int tag,mtag,cost_v,min_v; // 标记永久化与最短路径 
};

queue<int> que[4*N];
vector<pair<int,int>> vec[N];

struct SGT {
    Tre tre[4*N];

    void build(int now,int l,int r) {
        tre[now].l=l,tre[now].r=r;tre[now].min=tre[now].min_cost=INF;
        if(l==r) {tre[now].cost_v=tre[now].min_v=l;return;}
        build(lson,l,mid);build(rson,mid+1,r);
    }

    void pushup(int now) {
        if(tre[now].l==tre[now].r) {tre[now].min_cost=p[tre[now].tag]+tre[now].min,tre[now].mtag=tre[now].tag;return;}
        if(tre[lson].min<tre[rson].min) tre[now].min=tre[lson].min,tre[now].min_v=tre[lson].min_v;
        else tre[now].min=tre[rson].min,tre[now].min_v=tre[rson].min_v;
        tre[now].min_cost=min({tre[lson].min_cost,tre[rson].min_cost,p[tre[now].tag]+tre[now].min});
        if(tre[now].min_cost==tre[lson].min_cost) tre[now].cost_v=tre[lson].cost_v,tre[now].mtag=tre[lson].mtag;
        else if(tre[now].min_cost==tre[rson].min_cost) tre[now].cost_v=tre[rson].cost_v,tre[now].mtag=tre[rson].mtag;
        else tre[now].cost_v=tre[now].min_v,tre[now].mtag=tre[now].tag;
    }

    void change(int now,int p,int k) {
        if(tre[now].l>p || tre[now].r<p) return;
        if(tre[now].l==tre[now].r) {
            tre[now].min=k;
            pushup(now);
            return;
        }
        change(lson,p,k);change(rson,p,k);
        pushup(now);
    }

    void cgmin(int now,int l,int r,int k) { // 添加区间 
        if(tre[now].l>r || tre[now].r<l) return;
        if(tre[now].l>=l && tre[now].r<=r) {
            if(p[k]<p[tre[now].tag]) tre[now].tag=k;
            pushup(now);
            return;
        }
        cgmin(lson,l,r,k);cgmin(rson,l,r,k);
        pushup(now);
    }

    void init_que(int now,vector<Node>& vec) { // 初始化队列 
        vector<Node> L,R;
        for(auto& node:vec) {
            if(node.l<=tre[now].l && tre[now].r<=node.r) {
                que[now].push(node.p);
                continue;
            }
            if(node.l<=mid) L.push_back(node);
            if(node.r>mid) R.push_back(node);
        }
        if(!que[now].empty()) tre[now].tag=que[now].front();
        pushup(now);
        if(tre[now].l==tre[now].r) return;
        init_que(lson,L);init_que(rson,R);
        pushup(now);
    }

    void del(int now,int l,int r) { // 从队列中懒惰删除 
        if(tre[now].l>r || tre[now].r<l) return;
        if(tre[now].l>=l && tre[now].r<=r) {
            while(!que[now].empty() && vis[que[now].front()]) 
                que[now].pop();
            if(!que[now].empty()) tre[now].tag=que[now].front();
            else tre[now].tag=0;
            pushup(now);
            return;
        }
        del(lson,l,r);del(rson,l,r);
        pushup(now);
    }
};
SGT U,V;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> n >> m;
    p[0]=INF;
    for(int i=1;i<=n;++i) cin >> p[i];

    int x,l,r;vector<Node> v;
    for(int i=1;i<=m;++i) {
        cin >> x >> l >> r;
        vec[x].push_back({l,r});
        v.push_back({x,l,r});
    }

    U.build(1,1,n);
    V.build(1,1,n);

    sort(v.begin(),v.end(),[&](Node a,Node b) {
        return p[a.p]<p[b.p];
    });
    V.init_que(1,v);
    for(int i=1;i<=n;++i) U.change(1,i,p[i]);

    int nxt=1,ans=0;
    for(int i=1;i<=n;++i) {
        vis[nxt]=1;
        for(auto& [l,r]:vec[nxt]) {
            V.del(1,l,r);
            U.cgmin(1,l,r,nxt);
        }
        U.change(1,nxt,INF);
        V.change(1,nxt,p[nxt]);
        if(i==n) break;
        if(U.tre[1].min_cost<=V.tre[1].min_cost)
            ans+=U.tre[1].min_cost,nxt=U.tre[1].cost_v;
        else
            ans+=V.tre[1].min_cost,nxt=V.tre[1].mtag;
    }

    cout << ans << '\n';

    return 0;
}

时空复杂度均为 O(n \log n)，但是常数较大（时限 5s，最大测试点用时 874ms，远差于最优解的 141ms），希望能给大家提供一些新的解题思路。