有$N$個參賽者，每個參賽者有攻擊指數$a_i$和防禦指數$d_i$，每個參賽者可以往左或往右挑戰(可以往左往右一起來)，如果兩個指數中一個大於對手且另一個不小於對手(攻擊對攻擊，防禦對防禦)，那就會勝利。
如果勝利就能繼續往更左或更有挑戰，一路到沒有對手為止。
求最多勝場的參賽者的勝場數。
此時最大勝場數為8。
$1\le N\le 1.5\times 10^6, 0\le a_i,d_i\le 2\times 10^9$。
如果b能贏a且c能贏b則c能贏a，此時b能贏的人數決不會比c多。因此符合單調性。
維護一個非嚴格遞減的stack，對於每個元素pop掉stack中能贏過他們的，stack的top即為該元素可以往左挑戰到的最左端。
做一次從左到右和從右到左的聯集，之後取最大值即是答案。
複雜度$\mathcal{O}(N)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
signed main() {
EmiliaMyWife
int n;
cin >> n;
vector<int> atk(n), def(n), ans(n);
auto win = [&] (int a, int b) {
return ((atk[a] == atk[b] && def[a] >= def[b]) || (atk[a] > atk[b] && def[a] >= def[b]));
};
for(int i = 0; i < n; i++)
cin >> atk[i] >> def[i];
stack<int> st;
for(int i = 0; i < n; i++) {
while(st.size() && win(i, st.top()))
st.pop();
if(st.empty())
ans[i] += i;
else
ans[i] += i - st.top() - 1;
st.push(i);
}
st = stack<int>();
for(int i = n - 1; ~i; i--) {
while(st.size() && win(i, st.top()))
st.pop();
if(st.empty())
ans[i] += n - i - 1;
else
ans[i] += st.top() - i - 1;
st.push(i);
}
cout << *max_element(ans.begin(), ans.end()) << '\n';
return 0;
}
|