LCM Interval [TSG LIVE! 4 プログラミングコンテスト F]

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-lcm-interval

前提知識

• Disjoint Sparse Table
• 想定解はSliding Window Aggregationだが、本解法では使ってない

解法

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-lcm-interval/submissions/code/1317860248

左端を全探索して、その左端での最適な（最長な）右端を効率的に探すことで問題を解いていこう。
これは全ての区間に関する問題を解く時によく用いられる方針である。

LCMは区間を伸ばしていくと（広義）単調増加をする。
よって、X以下となる区間はある境界で分かれる。
ここを2分探索しよう。
この中で区間のLCMを計算する必要があるが、Disjoint Sparse Tableというデータ構造があり、これを使えばO(1)でいける。
正確にはLCM使うからO(log10⁹)。
これで区間の最長が得られるので、最適解を更新していくと答え。

int N, X, A[501010]; 
SparseTable<ll> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> A[i];

    vector<ll> v;
    rep(i, 0, N) v.push_back(A[i]);
    st.init(v);

    int ma = 0, ans1 = inf, ans2 = inf;
    rep(i, 0, N) {
        if (X < A[i]) continue;

        int ok = i, ng = N + 1;
        while (ok + 1 != ng) {
            int md = (ok + ng) / 2;
            if (st.get(i, md) <= X) ok = md;
            else ng = md;
        }

        int len = ok - i;
        if (ma < len) {
            ma = len;
            ans1 = i + 1;
            ans2 = ok;
        }
    }

    printf("%d %d\n", ans1, ans2);
}