D - タコヤキオイシクナール AtCoder Regular Contest 008

D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder

問題概略

N個の箱が一列に繋がって並んでおり、それらは実数(a,b)を持つ。

箱に数字を渡すとその数字は a * 渡された数 + bに変化して次の箱に渡される。

(a,b)は(1,0)で初期化されているが、M回値の更新が行われる

1を渡した時、すべての状態における結果の最大値と最小値を求めよ

制約

p_i (1≦p_i≦N) ボックス番号

 1≦N≦10¹², 0≦M≦100,000

a_i (−1≦a_i≦1)、b の値を表す実数 b_i (−1≦b_i≦1) 

解法

隣り合う２つの演算(a,b),(c,d)は(a * c , b * c + d)で一つにまとめられるためセグメント木を使えば良い。求めたい区間は端から端で固定されているため、一番上の値を返せばよくO(1)で求められ、アップデートはO(long n)で行ける。

また、Nがやばい大きい事と、(1,0)は答えに影響を与えないのでM個のボックスがある問題だとみなせる。

longの箱の場所とそれが与えられた中で前から何番目かを紐付ければ解ける。

class SegmentTakoyaki
{
    double[] a, b;

    int N;

    SegmentTakoyaki(int n)
    {
        N = 1;
        while (n > N) N *= 2;
        a = new double[N * 2];
        b = new double[N * 2];
        Arrays.fill(a, 1);
        Arrays.fill(b, 0);
    }

    public void update(int id, double av, double bv)
    {
        id = id + N - 1;
        a[id] = av;
        b[id] = bv;

        while (id > 0)
        {
            id = (id - 1) / 2;
            double la = a[id * 2 + 1];
            double lb = b[id * 2 + 1];
            double ra = a[id * 2 + 2];
            double rb = b[id * 2 + 2];
            a[id] = la * ra;
            b[id] = lb * ra + rb;
        }
    }

    public double calcTaste()
    {
        return a[0] + b[0];
    }


}


public class Main
{
    static StringBuilder sb = new StringBuilder();
    static FastScanner sc = new FastScanner(System.in);
    static int INF = 12345678;
    static long LINF = 123456789123456789L;
    static long MINF = -123456789123456789L;
    static long MOD = 1000000007;
    static int[] y4 = {0, 1, 0, -1};
    static int[] x4 = {1, 0, -1, 0};
    static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
    static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
    static long[] F;//factorial
    static boolean[] isPrime;
    static int[] primes;
    static char[][] map;

    static int M;
    static long N;
    static int[] A;


    public static void main(String[] args)
    {
        N = sc.nextLong();
        M = sc.nextInt();
        if (M == 0)
        {
            System.out.println(1);
            System.out.println(1);
            return;
        }
        long[] p = new long[M];
        double[] a = new double[M];
        double[] b = new double[M];
        //値を読み込む
        TreeSet<Long> lindexes = new TreeSet<>();
        for (int m = 0; m < M; m++)
        {
            p[m] = sc.nextLong() - 1;
            a[m] = sc.nextDouble();
            b[m] = sc.nextDouble();
            lindexes.add(p[m]);
        }
        //longの値が前から何番目か紐づけたい
        HashMap<Long, Integer> ltoi = new HashMap<>();
        int index = 0;
        for (Long lindex : lindexes)
            ltoi.put(lindex, index++);
        //核
        SegmentTakoyaki st = new SegmentTakoyaki(M);
        double min = 1;
        double max = 1;
        for (int i = 0; i < M; i++)
        {
            //i番目のクエリのインデックスは前からどこか
            int pi = ltoi.get(p[i]);
            double av = a[i];
            double bv = b[i];
            st.update(pi,av,bv);

            double score = st.calcTaste();
            min = Math.min(min, score);
            max = Math.max(max, score);
        }
        System.out.println(min);
        System.out.println(max);
    }