ProductThreshold [2018 TCO Algorithm Round 3A Div1 Med]

http://community.topcoder.com/stat?c=problem_statement&pm=14949

与えられたシードによって作られる負や0の可能性もある配列Aがある。
この配列の連続する部分列において、総積がlimit以下であるのは何通りあるか。

前提知識

• しゃくとり法

解法

シード通りに配列Aを作ろう。
　
左端を固定して、満たすものを数え上げるいつものテクをしよう。
左端をlとする。
lから右に部分列を伸ばしていって最初に0が来るところを探そう。
zeros配列を作っておき、しゃくとり法のように0が来る所を更新していく。これをzero[idx]とする。
右に部分列を伸ばしていって総和の絶対値がlimitを始めて超える所をrとする。
これもしゃくとり法で計算できる。
すると、[l,r)の範囲では絶対値がlimit以下なので、全て条件を満たす。
[r,zero[idx])の範囲では総積が負となる場合が条件を満たす。
[zero[idx],N)の範囲では総積が0となるので、全て条件を満たす。
1番目と3番目は範囲の長さを取るだけなので、簡単。
　
問題は[r,zero[idx])の範囲では総積が負となる場合であるが、
先頭から負の数が来たら0と1を切り替えて格納した配列をpmとする。
0＜A[l]であれば符号が入れ替わる必要があるので[r,zero[idx])の中でpmの値が1-pm[l]である数を数えればいい。
A[l]＜0であれば符号は入れ替わらない必要があるので[r,zero[idx])の中でpmの値がpm[l]である数を数えればいい。
2つとも累積和を使えば計算できる。

int N, L; vector<int> A;
int pm[101010], sm[2][101010];
int get(int l, int r, int pa) {
    int res = 0;
    if (r) res += sm[pa][r - 1];
    if (l) res -= sm[pa][l - 1];
    return res;
}
ll solve() {
    ll ans=0;

    vector<int> zeros;
    rep(i, 0, N)if (A[i] == 0)zeros.push_back(i);
    A.push_back(0);
    zeros.push_back(N);

    int p = 0;
    rep(i, 0, N) {
        if (A[i] == 0) {
            pm[i] = -1;
        } else {
            if (A[i] < 0) p = 1 - p;
            pm[i] = p;
        }
    }
    rep(pa, 0, 2)rep(i, 0, N)sm[pa][i] = 0;
    rep(i, 0, N)if (0 <= pm[i])sm[pm[i]][i]++;

    rep(pa, 0, 2)rep(i, 1, N)sm[pa][i] += sm[pa][i - 1];

    int idx = 0;
    ll x = 1;
    int r = -1;
    rep(l, 0, N) {
        if (A[l] == 0) {
            ans += N - l;
            idx++;
            continue;
        }

        // for zero
        ans += N - zeros[idx];

        if (r < l) {
            r = l;
            x = abs(A[r]);
        }

        while (1 <= x and x <= L) {
            r++;
            x *= abs(A[r]);
        }

        ans += r - l;

        if (0 < A[l]) ans += get(r, zeros[idx], 1-pm[l]);
        else ans += get(r, zeros[idx], pm[l]);

        x /= abs(A[l]);
    }
    return ans;
}
struct ProductThreshold {
    long long subarrayCount(int _N, int limit, vector <int> Aprefix, int spread, int offset) {
        L = limit;
        N = _N;
        A.clear();
        fore(a, Aprefix) A.push_back(a);
        ll seed = abs(A.back());
        int i;
        for (i = Aprefix.size(); i<N; i++) {
            seed = (seed * 1103515245LL + 12345) % (1LL << 31);
            A.push_back(seed%spread + offset);
        }

        return solve();
    }
};