CF1437D

Description

Monocarp有一棵树，可是他已经忘记了它的形态。但是他有这棵树的$bfs$序，并且对于每一个节点，$bfs$都会按照升序遍历它的子节点。现在给出这个$bfs$序，求出这棵树的最小深度。

Solution

先观察一下这个BFS序的性质

因为它给的BFS是按照升序访问子节点的，那么对于每个点后面出现的节点，如果它后面的点比他的编号还小，说明要新开一层，否则就可以一直堆在一层

举个例子：1 4 3 2

1已经确定是根，那么1的第一个子节点就是4，观察到4是目前1的子节点中编号最小的，如果我们要把2也弄成1的子节点，那么按照BFS序，2应该在4前面出现，所以这样是不合法的，说明2要新开一层成为4的子节点

Code

#include <bits/stdc++.h>
using namespace std;
 
const int SIZE = 2e5 + 5;
 
int T, n, ans;
int a[SIZE], dep[SIZE];
 
inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}
 
inline void bfs()
{
    std::queue < int > q;
    memset(dep, 0, sizeof(dep));
    q.push(1);
    int pos = 2;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans = std::max(ans, dep[u]);
        int lst = pos;
        if (pos > n) break;
        while (a[pos + 1] > a[pos] && pos < n) ++ pos;
        for (int i = lst; i <= pos; ++ i) {
            dep[a[i]] = dep[u] + 1;
            q.push(a[i]);
        }
        ++ pos;
    }
}
 
int main()
{
    T = read();
    while (T --) {
        n = read();
        for (int i = 1; i <= n; ++ i) a[i] = read();
        ans = 0;
        bfs();
        for (int i = 1; i <= n; ++ i) ans = std::max(ans, dep[i]);
        printf("%d\n", ans);
    }
    return 0;
}