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;
}