CF 319B Psychos in a Line 【单调队列】

维护一个单调下降的队列。

对于每一个人，只需要找到在他前面且离他最近的可以杀掉他的人即可。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 100005
vector<int> v;
int f[N], n, t, cnt;int main() {
scanf("%d", &n);
memset(f, 0, sizeof(f)); for (int i=0; i<n; i++) {
scanf("%d", &t);
cnt = 0;
if (v.size() == 0) { v.push_back(t); continue; }
while (v.back() < t) {
cnt = max(cnt, f[v.back()]);
v.pop_back();
if (v.size() == 0) break;
}
if (v.size() == 0) { v.push_back(t); continue; }
f[t] = cnt + 1;
v.push_back(t);
} int ans = 0;
for (int i=0; i<n; i++) ans = max(ans, f[i]);
printf("%d\n", ans); return 0;
}