前提知識

解説

複合的な知識が必要。

まずは、全探索対象が区間となっているが、区間の全探索は間に合わない。
そこで、主客転倒をして全探索対象が変えられないか考えてみる。
つまり、「全部の区間についてAの総積の更に総積をとる」というのを「A×(Aが含まれる区間の個数)の総積」に置き換えて考える。
Aが含まれる区間の個数が分かれば、A[i]の区間の個数乗の総積が答えとなる。

これで区間の個数が高速に求められれば、A[i]の全探索で答えが導けることは分かったが、区間の個数を求めるのはどうやればいいだろう。
条件を満たす区間の個数を求めるときのテクとして、片方を全探索して、条件を満たすもう片方を高速に求めるテクがある。
このテクはかなり良く出てくるので、思いつきたい。

左端を全探索するとして、条件を満たす右端を左端から初めて順番に考えてみると、「満たす満たす満たす満たさない満たさない」のように
前半は満たすけど、後半は満たさないといった感じになる。
つまり、二分探索を使って境界線を探すことができるということである。
ここで、区間の総積を区間積セグメントツリー（か、より計算量の良いスパーステーブル）で求められるようにしておくことで、
二分探索で条件を満たす区間を割り出すことができる。
これで、[l,l], [l,l+1], ..., [l,r]は条件を満たすということを割り出せる。
なお、この部分は尺取り法の方が計算量がいい。
全探索＋二分探索は尺取り法で改善できるのはよくある話であり、こちらも練習しておくといいだろう。
あと、オーバーフローしないように注意。

この区間でAがどれだけ使われているか、個数を見てみると、5 4 3 2 1のような公差-1のような数列になっている。
全ての右端について、この公差-1のような数列を全部求めて足し合わせれば、それぞれのAについて区間の個数が求められる。
このような一次関数を高速に数列に足しこむテクとして、imos法がある。
定数を数列に足しこむテクとしてimos法を認識している人も多いと思うが、一次関数や二次関数も実は足しこむことができる。
一次関数であれば二回累積和をする。
具体的には公差a, 初項bを区間[L,R)に足しこむ場合は、
v[L] += a
v[R] -= a
をして一回、累積和を取る。
その後、
v[R] -= (R - L - 1) * a
v[L] += b
v[R] -= b
をして、更に累積和を取る。

これで、各Aの出てくる回数が分かったので、累乗を取って、総積を取ると答え。

int N; ll A[101010];
SparseTable<ll> st;
ImosLinear<ll> imos;
int limit = 1000000000;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) if (A[i] == 0) {
        cout << 0 << endl;
        return;
    }

    st.init(A, A + N);
    imos.init(N);

    rep(l, 0, N) {
        int ok = l + 1, ng = N + 1;
        while (ok + 1 != ng) {
            int md = (ok + ng) / 2;
            if (st.get(l, md) < limit) ok = md;
            else ng = md;
        }
        imos.set(l, ok, -1, ok - l);
    }

    imos.build();

    mint ans = 1;
    rep(i, 0, N) ans *= mint(A[i]) ^ imos[i];
    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

積の積 [yukicoder 1084]

前提知識

解説