题解：P12018 [NOISG 2025 Finals] 机器人

· · 题解

Statement

Link

当然这个题面非常难以理解。我们可以把这道题理解为一个 DAG 上的问题，这样就更加方便理解了。

DAG 版本的题面：

一个 (h+2)\times(w+2) 的棋盘中有若干个格子上可能有结点。结点一共有三种：

第 0 列布满结点，为起始结点。起始结点有一个出边指向这一行（除自己外）最靠左的结点（可能是中间结点或者终点结点）。

第 w+1 列布满结点，为终止结点。终止结点没有出边。

非边缘的方格内，每一列有一个中间结点，这个结点有两个出边，分别指向上一行和下一行中，自己右边的结点中最靠左的一个。

每次询问给定一个起始结点的区间，求最小的（子树个数最少的），包含这些起始结点的，以终止结点为根的森林。

（还是有点怪）

（因为边只会往右，所以这个题是 DAG。）

绿色圆圈是起始结点，紫色是中间结点，黑色是终止结点，蓝色 / 红色是 DAG 中的边，粉色是从 1 开始的极大子树。（1-3 可以到达同一个终点，但是 1-4 不可以）

Solution

注意到如果起始 i 能够向下到达终止 j(i<j)，那么下面的的起始 i+1 也一定能够到达。向上同理。因此，如果 l, r 能够到达同一个终点， [l, r] 中间的所有节点都能够到达同一个终点。所以最终的几个不交的子树在区间上也是不交的。

那么考虑一个简单的贪心，从最上面开始取，每次取最大的可能子树，这样总共的区间数一定是最小的。

我们只需要预处理出每个起始结点能到达的最高和最低终点结点就可以预处理出这个极大子区间。

这个东西 dp 或者记忆化都可以做。

最后要注意最终答案可能是非常多的不交的区间，因此要倍增来保证时间复杂度。

Code

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int _ = 2e5+50;
int h, w, q, ql, qr, cur;
class node{ // 结点类
    private:
        bool isend = 0; // 是否是终止结点
        int row; // 第几行
        node *ls, *rs; // 出边指向的结点
        int minans = -1, maxans = -1; // 记忆化（其实没必要）
    public:
        node(bool end, int Rrow, node *LS = nullptr, node *RS = nullptr){
            isend = end, row = Rrow, ls = LS, rs = RS;
            if(isend) minans = maxans = Rrow;
        }
        int minreach(){ // 最上面能到哪一行
            if(minans == -1) return minans = ls->minreach();
            else return minans;
        }
        int maxreach(){ // 最下面能到哪一行
            if(maxans == -1) return maxans = rs->maxreach();
            else return maxans;
        }
};

int subtree[_][20]; // subtree [i][k] 表示从 i 开始后的 2^k 个，相邻的，不交的，极大子树的最后一个起始节点
                    // 或者说从 i 开始到 i + 2^k - 1 恰好能用 2^k 个终点完全覆盖

int main(){

    ios::sync_with_stdio(0),
    cin.tie(0), cout.tie(0);
    cin >> h >> w;

    vector<node> beginr, endr, midr;// 初始，结束和中间
    beginr.reserve(h+2), endr.reserve(h+2), midr.reserve(w);

    vector<node*> frontr (h+2);
    for(int i = 0; i <= h+1; i++)
        endr.push_back(node(true, i, nullptr, nullptr)), frontr[i] = &endr[i];
    vector<int> ix (w);
    for(auto & ixx: ix)
        cin >> ixx;
    reverse(ix.begin(), ix.end());
    for(auto & ixx: ix){
        midr.push_back(node(false, ixx, frontr[ixx-1], frontr[ixx+1])), // 建红色的边
        frontr[ixx] = &midr.back();
    }
    for(int i = 0; i <= h+1; i++)
        beginr[i] = node(false, i, frontr[i], frontr[i]); // 建绿色的边

    for(int i = 1, j = 1; i<= h; i++){ // 初始化倍增 [0] 
        while(beginr[j].minreach() <= beginr[i].maxreach() && j <= h) 
            ++ j;
        subtree[i][0] = j-1;
    } // 

    for(int k = 1; (1<<k) <= h; k++){ // 倍增
        subtree[h+1][k-1] = subtree[h+2][k-1] = subtree[h+1][k] = subtree[h+2][k] = h+1;
        for(int i = 1; i <= h; i++){
            subtree[i][k] = subtree[subtree[i][k-1]+1][k-1];
        }
    } // 

    cin >> q;
    while(q--){
        cin >> ql >> qr, cur = 0;
        while(ql < qr){
            for(int k = 20; k >= 0; k--){
                if((1<<k) > h) continue;
                if(subtree[ql][k] < qr){
                    ql  = subtree[ql][k] +1, cur += (1<<k);
                }
            }
            if(subtree[ql][0] >= qr)
                break;
        }
        cout << cur+1 << endl;
    }

}