Range High-Element Query [yukicoder 878]

https://yukicoder.me/problems/no/878

前提知識

• ダブリング

解説

https://yukicoder.me/submissions/377919

高い要素の個数を答える方針でしばらく考えていてダメだったので、
ちょっと言い換えを考えてみる。
区間が与えられた時に、先頭から順に最も近い今いる場所より大きい数の所へジャンプすることにする。
このとき区間内で行えるジャンプ回数+1が答えになっている。
よって、何回ジャンプできるかを見ればいい。
それはダブリングでできる。
dp[p][cu] := A[cu]から2^p回ジャンプした時に到達する場所
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);
    }
}