TIOJ 2201：糖豆人改（Fallguys）

TIOJ 2201：糖豆人改（Fallguys）

題目大意：有 $n$ 個人，能力值為相異的 $n$ 個數字 $a_1\sim a_n$，有 $q$ 筆詢問，每筆詢問有 $l_i, r_i$，代表想要讓區間 $[l_i, r_i]$ 的人進行遊戲，每輪遊戲只要比相鄰的人能力值都大，就可以晉級下一輪，直到剩一人為止，問你會進行幾輪。

解法：我們一開始可以先對所有人進行模擬，每輪遊戲人數至少會少一半，最多進行 $\log(n)$ 輪，我們可以紀錄 $tl_{i, j}, tr_{i, j}$，代表在第 $j$ 輪在 $i$ 左(右)邊，且離 $i$ 最近存活的人。我們維護兩個變數 $vl, vr$，代表兩端的能力值，假設現在區間裡面兩端的人是 $l, r$，第二近的是 $pl, pr$，那區間 $pl, pr$ 的變動情況會跟所有人遊戲的變動情況一樣，只要去考慮 $vl, vr, a_l, a_r$ 就可以了，因為所有人遊戲時會跟區間外的人比較到的只會有 $vl, vr, a_l, a_r$，裡面的一定是跟區間內的人比。時間複雜度 $O((n+q)\times\log(n))$

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5e5 + 5;
const int H = __lg (SIZE) + 2;

int n, m, q;
int a[SIZE];
int tl[SIZE][H], tr[SIZE][H];

int cal (vector<int> v) {
    int cnt = 0;
    while (v.size() > 1) {
        cnt++;
        vector<int> u;
        for (int i = 0; i < v.size(); i++) {
            if ((i == 0 || v[i] > v[i - 1]) && (i == v.size() - 1 || v[i] > v[i + 1])) u.pb (v[i]);
        }
        v = u;
    }
    return cnt;
}

void solve() {
    cin >> n >> q;
    vector<pair<int, int>> v;
    FOR (i, 1, n) {
        cin >> a[i];
        v.pb (i, a[i]);
        tl[i][0] = tr[i][0] = i;
    }
    tr[0][0] = 1;
    tr[n + 1][0] = n + 1;
    tl[n + 1][0] = n;
    while (v.size() > 1) {
        m++;
        vector<pair<int, int>> u;
        for (int i = 0; i < v.size(); i++) {
            if ((i == 0 || v[i].S > v[i - 1].S) && (i == v.size() - 1 || v[i].S > v[i + 1].S)) u.pb (v[i]);
        }
        v = u;
        for (int i = 0; i < v.size(); i++) {
            for (int j = (i == 0 ? 0 : v[i - 1].F + 1); j <= v[i].F; j++) tr[j][m] = v[i].F;
            for (int j = (i == v.size() - 1 ? n + 1 : v[i + 1].F - 1); j >= v[i].F; j--) tl[j][m] = v[i].F;
        }
        for (int j = v.back().F + 1; j <= n + 1; j++) tr[j][m] = n + 1;
    }
    while (q--) {
        int l, r, ans = 0;
        cin >> l >> r;
        int vl = 0, vr = 0;
        while (1) {
            if (l == r) {
                if (vl && vr) ans += (min (vl, vr) > a[l]) + 1;
                else if (vl || vr) ans++;
                break;
            }
            int pl = tr[l + 1][ans], pr = tl[r - 1][ans];
            if (pl > pr) {
                vector<int> v;
                if (vl) v.pb (vl);
                v.pb (a[l]), v.pb (a[r]);
                if (vr) v.pb (vr);
                ans += cal (v);
                break;
            }
            if (vl < a[l]) vl = a[l] > a[pl] ? a[l] : 0;
            if (vr < a[r]) vr = a[r] > a[pr] ? a[r] : 0;
            ans++;
            l = tr[pl][ans], r = tl[pr][ans];
            if (l > r) {
                ans += vl && vr;
                break;
            }
        }
        cout << ans << '\n';
    }
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！