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}$,歡迎追蹤!
留言
張貼留言