某島

… : "…アッカリ~ン . .. . " .. .
June 27, 2022

Codeforces Global Round 21

傳送門

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. 滿足初始條件

三組條件即可。