TCO18 R3A Medium ProductThreshold

http://community.topcoder.com/stat?c=problem_statement&pm=14949 TCO18 Algorithm Round 3A Editorials - Topcoder 2.0

問題

積がlimit以下になるような連続した部分列の数を求めよ

解法

0を含む区間は条件を満たすので、0を含む区間だけ先に計算し、以後0を含まない区間のみ計算する。 ある区間の積を考えたときに条件を満たさない可能性があるのは区間の積が正のときだけ。

cnt(s,i)[0,i)の積の符号がsとなるiの数とする。 積が負になる場合は必ずlimit以下となるので、s[0,i)の積の符号とすると、積の絶対値がlimit超えないように尺取りしつつ\displaystyle \sum_{l,r} cnt(-s,r)+cnt(s,r)-cnt(s,l)で条件を満たす区間の数が求まる。

一言

配列は乱数で生成するので手を抜いても大丈夫かと思ったが駄目なケースがあった。

package main.tasks;

import java.util.*;

public class ProductThreshold {
    public long subarrayCount(int N, int limit, int[] Aprefix, int spread, int offset) {
        long[] ary = new long[N];
        for (int i = 0; i < Aprefix.length; i++) {
            ary[i] = Aprefix[i];
        }
        long seed = Math.abs(ary[Aprefix.length - 1]);
        for (int i = Aprefix.length; i < N; i++) {
            seed = (seed * 1103515245 + 12345) & ((1L<<31)-1);
            ary[i] = seed % spread + offset;
        }
        return solve(N, limit, ary);
    }

    long solve(int N, int limit, long[] ary) {
        List<Integer> zero = new ArrayList<>();
        zero.add(-1);
        for (int i = 0; i < N; i++) {
            if (ary[i] == 0) zero.add(i);
        }
        long ans = 0;
        for (int idx = 1; idx < zero.size(); idx++) {
            long i = zero.get(idx - 1);
            long j = zero.get(idx);
            long k = zero.get(idx);
            ans += (N - k) * (j - i);
        }

        sum = new long[2][N+1];
        zero.add(N);
        for (int i = 0; i + 1 < zero.size(); i++) {
            ans += solve(zero.get(i) + 1, zero.get(i + 1), limit, ary);
        }
        return ans;
    }

    long[][] sum;
    long solve(int l, int r, int limit, long[] ary) {
        long ans = 0;
        sum[0][l] = sum[1][l] = 0;
        long mul = 1;
        for (int i = l, j = l, p = 0; j < r; j++) {
            sum[p][j+1]++;
            for (int k = 0; k < 2; k++) sum[k][j+1] += sum[k][j];
            if (ary[j] < 0) p ^= 1;
            mul *= ary[j];
            for (; Math.abs(mul) > limit; i++) {
                mul /= ary[i];
            }
            ans += sum[p^1][j+1] + sum[p][j+1] - sum[p][i];
        }
        return ans;
    }

    static void dump(Object... o) { System.err.println(Arrays.deepToString(o)); }
}