F - Min-First Search Editorial by en_translator Editorial for printing
Let tree \(T\) be a rooted tree rooted at vertex \(1\). Write the parent of \(v\ (2\le v\le N)\) as \(p _ v\). Then, among the steps in the problem statement, “inserting the vertices adjacent to \(x\) not contained in \(P\) yet into \(S\)” can be interpreted as inserting the children of vertex \(x\) to \(S\).
For two vertices \(u\) and \(v\), suppose \(u\gt v\), and \(p _ v\) is added to \(P\) prior to \(u\). Then, in order for \(u\) to be picked as the minimum value, \(v\) must have been picked already, so \(v\) must be appended earlier than \(u\) into \(P\).
In other words, if \(u\gt v\), and \(u\) occurs earlier than \(v\) in \(P\), then \(u\) must have appeared at the same moment as or before reaching \(p _ v\).
For \(2\le i\le N\), let \(m _ i\) be the maximum \(j\) such that \(Q _ j\gt Q _ i\) and \(j\lt i\) (or \(0\) if there is no such \(j\)). By the discussion above, \(p _ {Q _ i}\) must be one of \(Q _ {m _ i},Q _ {m _ i+1},\ldots,Q _ {i-1}\).
Conversely, if \(p _ {Q _ i}\) falls into one of them for all \(i\ (2\le i\le N)\), then \(f(T)=P\). (It suffices to proved that no element occurs earlier than the position in \(P\), which can be easily shown.)
Since \(m _ i\) is independent of the other choices of \(p _ j\), one can freely choose \(p _ {Q _ i}\) for each \(i\). Hence, the answer is \(\displaystyle\prod _ {i=2} ^ N(i-m _ i)\).
Naively finding \(m _ i\) may cost a worst time complexity of \(\Theta(N ^ 2)\), which might be hard to meet the execution time limit. Here, by definition of \(m _ i\), we have \(Q _ j\lt Q _ i\) for all \(j\) with \(m _ i\lt j\lt i\), so we obtain the following algorithm:
- Initially, let \(x\leftarrow i-1\).
- While \(0\le x\) and \(Q _ x\lt Q _ i\), set \(x\leftarrow m _ x\).
- The resulting \(x\) is the sought \(m _ i\).
Here, let \(m _ 1\) be \(0\) for convenience.
For each \(t\ (1\le t\le N)\), the transition \(t\leftarrow m _ t\) occurs at most once, so the total time complexity is \(O(N)\).
The following is sample code.
#include <iostream>
#include <vector>
#include <atcoder/modint>
int main() {
using namespace std;
using modint = atcoder::static_modint<998244353>;
unsigned N;
cin >> N;
vector<unsigned> Q(N);
for (auto&& q : Q) {
cin >> q;
--q;
}
modint ans{1};
vector<unsigned> prev_greater(N);
for (unsigned i{1}; i < N; ++i) {
unsigned p{i - 1};
while (p && Q[p] < Q[i]) p = prev_greater[p];
prev_greater[i] = p;
ans *= i - p;
}
cout << ans.val() << endl;
return 0;
}
posted:
last update: