https://yukicoder.me/problems/no/878
前提知識
解説
https://yukicoder.me/submissions/377919
高い要素の個数を答える方針でしばらく考えていてダメだったので、
ちょっと言い換えを考えてみる。
区間が与えられた時に、先頭から順に最も近い今いる場所より大きい数の所へジャンプすることにする。
このとき区間内で行えるジャンプ回数+1が答えになっている。
よって、何回ジャンプできるかを見ればいい。
それはダブリングでできる。
dp[p][cu] := A[cu]から2p回ジャンプした時に到達する場所
dp[0][cu]ができていれば、それ以降の更新は難しくない。
問題はここだ。
最も最寄りなA[cu]より大きい数の場所をいかに特定するか。
区間最大セグメントツリー上で二分探索をしよう。
int N, Q, A[101010]; int dp[17][101010]; SegTree<int, 1 << 17> st; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> Q; rep(i, 0, N) cin >> A[i]; rep(i, 0, N) st.update(i, A[i]); rep(p, 0, 17) rep(cu, 0, N + 1) dp[p][cu] = N; rep(cu, 0, N) { if(A[cu] < st.get(cu, N)) { int ok = N, ng = cu; while(ng + 1 != ok) { int md = (ng + ok) / 2; if(A[cu] < st.get(cu, md)) ok = md; else ng = md; } dp[0][cu] = ok-1; } } rep(p, 1, 17) rep(cu, 0, N) dp[p][cu] = dp[p - 1][dp[p - 1][cu]]; rep(i, 0, Q) { int t, l, r; cin >> t >> l >> r; l--; r--; int ans = 1; int p = 16; int pp = 1; rep(i, 0, 16) pp *= 2; int cu = l; while (0 <= p and cu <= r) { int to = dp[p][cu]; if(to <= r) { ans += pp; cu = to; } p--; pp /= 2; } printf("%d\n", ans); } }