传送门

• https://codeforces.com/contest/1696
• https://zhuanlan.zhihu.com/p/533890061

Problem D. Permutation Graph

给定一个排列 A ，排列的每个位置对应图中的一个节点，如果一段区间的端点上的数恰好等于这个区间的两组最值，那么我们就给这两个端点位置之间连一条无向边。
问从位置 1 出发到位置 n 的最短路。

这个题有两种做法。。做法 1。。

只要考察路径上的必经之点。。不失一般性，我们考察最小数。。。
假设位置为 p，那么最后的路径一定经过这个位置，因为 p 左右两边互不联通，那么我们显然可以用 p 进行递归，变成 [0, p] 和 [p, n) 两个子问题，且两边对称，我们考虑 [0, p] 这个子问题。
和开始的状态稍微不同，因为我们知道最右侧必然是最大数，因此这一次我们要找 [0, p] 区间的最小数，设位置为 x，那么再次分割成 [0, x] 和 [x, p] 两个子问题。
其中 [x, p] 最大值和最小值都在两侧，直接返回 1，而 [0, x] 是一个结构一样的子问题，于是结束，整个算法只需要预处理前缀和后缀的最小、最大值和对应下标即可，复杂度 O(n)，非常简单。

const int N = int(5e5) + 9;
int a[N], n; PII l[2][N], r[2][N];

int f(PII s[][N], bool b, int x) {
    int p = s[b][x].se; if (x == p) return 0;
    return 1 + f(s, b^1, p);
}

int gao() {
    RD(n); REP(i, n) RD(a[i]);
    l[0][0] = l[1][0] = {a[0], 0};
    FOR(i, 1, n) {
        l[0][i] = min(l[0][i-1], {a[i], i});
        l[1][i] = max(l[1][i-1], {a[i], i});
    }
    r[0][n-1] = r[1][n-1] = {a[n-1], n-1};
    DWN(i, n-1, 0) {
        r[0][i] = min(r[0][i+1], {a[i], i});
        r[1][i] = max(r[1][i+1], {a[i], i});
    }

    int p = l[0][n-1].se;
    return f(l, 1, p) + f(r, 0, p);
}


int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    Rush OT(gao());
}

做法 2。。。做法 2 基于这样的结论，算法运行过程中，一定只需要不断往右走，不需要返回。。。
（这个结论实际上比做法 1 的结论弱。。。而且不用做法 1 的方式证。。也其实更麻烦。。。证明可以考察某个点 x，如果它向某个方向，例如右边，连接了 r0, r1, r2… 一组点，那么这些点一定构成一个递增或者递减序列。。因此自然 r 序列之间也互相连通，因此直接连到最远的点更优。）

无论如何，考虑这个做法。。从 1 出发，每次移动到最远的点。方法是，假设当前点为 x，那么考察 x 和 x+1 的大小关系，不失一般性，假设 a[x] < a[x+1]，那么我们先要找到后缀里的第一个比 a[x] 小的数，假设是 p，之后我们要找一个从 x 出发的，不超过位置 p 的连续递增序列所能到达的最远位置 r，x = r 并迭代到下一步即可。我们只需要预处理出，每个数向右，第一个小于它和第一个大于它的位置分别在哪里即可。..
这个是栈 or 笛卡尔树的基本操作。。。https://oi-wiki.org/ds/cartesian-tree/

上次遇到笛卡尔树的题似乎是 #759 的 F？

2.1 栈版本

const int N = int(5e5) + 9;
int a[N], n; int r[2][N];

int gao() {
    RD(n); REP(i, n) RD(a[i]);
    stack<int> s[2];
    a[n] = -INF; s[0].push(n);
    a[n+1] = INF; s[1].push(n+1);

#define rr r[b][i]
    DWN(i, n, 0) REP(b, 2) {
        while ((a[i] < a[s[b].top()]) ^ b) s[b].pop();
        rr = s[b].top(); s[b].push(i);
    }

    int z = 0;

    for (int i=0;i!=n-1;++z) {
        bool b = a[i] > a[i+1]; int r0 = rr; b ^= 1;
        while (rr < n && rr < r0) i = rr;
    }

    return z;
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    Rush OT(gao());
}

2.2 笛卡尔树

const int N = int(5e5) + 9;
int a[N], n; int r[2][N];

#define rr ::r[b][i]

namespace Cartesian_Tree{
    int l[N], r[N], p[N];
    int lc[N], rp[N];
    #define lx l[x]
    #define rx r[x]
    #define ly l[y]
    #define ry r[y]
    void dfs(int x) {
        if (!x) return;
        rp[lx] = x; rp[rx] = rp[x];
        dfs(lx); dfs(rx);
    }
    void build(bool b) {
        a[0] = b ? n+1 : 0;
        FOR_1(x, 0, n) rx = 0;
        REP_1(x, n) {
            int y = x-1; while ((a[y] > a[x]) ^ b) y = p[y];
            p[lx = ry] = x; p[ry = x] = y;
        }
        rp[r[0]] = n+1; dfs(r[0]);
    }
    void init() {
        REP(b, 2) {
            build(b);
            REP_1(i, n) rr = rp[i];
        }
    }
};

int gao() {

    RD(n); REP_1(i, n) RD(a[i]);
    Cartesian_Tree::init();

    int z = 0;

    for (int i=1;i!=n;++z) {
        bool b = a[i] > a[i+1]; int r0 = rr; b ^= 1;
        while (rr <= n && rr < r0) i = rr;
    }

    return z;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    Rush OT(gao());
}

Problem F. Tree Recovery

给一个 n <= 100 的树，告诉你所有点对最短路径之间的相等关系。
要求重构这颗树

感觉 TC 肯定出过类似的题？一般感觉这种题应该是复杂的构造？
不过这个题可以直接 O(n4) 暴力。。。我们以所有路径的相等关系建立并查集，如果存在解，那么树中的 n-1 边必然组成一个恰好 size = n-1 的连通块。

于是我们直接暴力合并，之后检查连通块是否恰好满足，
1. size = n-1
2. 构成一颗树
3. 满足初始条件

三组条件即可。