E - Decrease (Judge ver.) AtCoder Regular Contest 079

E: Decrease (Judge ver.) - AtCoder Regular Contest 079 | AtCoder

問題概略
長さNの非負整数列aに対して、数列の最大値がN-1以下になるまで以下の操作を繰り返し行う。
数列の最大値を一つ選びN減らす。それ以外の値を1増やす

上の操作は何回行われるか。

制約
2 <= N <= 50
0 <= ai <= 10^16 +1000

解法

セグ木で殴る

途中で最大値がN未満にならない限り自由に数を選んで良さそうです。
なので、最大値を選び、その数が10^4未満になるようにまとめて削り、その分他の数を増やします。
これは、最大値のインデックスを取得でき、区間に加算ができる遅延評価セグメント木を使えば出来ます。
上の操作をすべての要素が10^4未満になるまでやってみます。

今、全ての要素は10^4未満であり全体の合計は高々5*10^5です、問題の操作をするたびに全体の合計は1減るため、セグメント木を使えばO(10^5)で操作出来ます
Submission #3320576 - AtCoder Regular Contest 079 | AtCoder

  static int N;
  static long[] A;

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        A = nla(N);
        long cou = 0;
        //セグ木
        SegmentAdd s = new SegmentAdd(A);
        int lim = (int) 2e4;
        //とりあえずlimまで減らす
        while (true) {
            if (s.max(0, N) <= lim) break;
            int maxi = s.maxi(0, N);
            long v = s.sum(maxi, maxi + 1);
            long kai = (v - lim) / N + 10;
　　　//最大値を削る
            s.add(maxi, maxi + 1, -kai - (kai * N));
            //全体を増やす
            s.add(0, N, kai);
            cou += kai;
        }
        while (s.max(0, N) >= N) {
            int maxi = s.maxi(0, N);
            s.add(0, N, 1);
            s.add(maxi, maxi + 1, -N - 1);
            cou++;
        }
        System.out.println(cou);
    }

    static class SegmentAdd {
        int n;
        long[] sum, min, max, lazy;
        int[] mini, maxi;

        SegmentAdd(int size) {
            n = 1;
            while (n < size) n *= 2;
            sum = new long[2 * n - 1];
            min = new long[2 * n - 1];
            max = new long[2 * n - 1];
            lazy = new long[2 * n - 1];
            mini = new int[2 * n - 1];
            maxi = new int[2 * n - 1];
            Arrays.fill(min, Long.MAX_VALUE);
            Arrays.fill(max, Long.MIN_VALUE);
            for (int i = 0; i < n; i++) {
                mini[i + n - 1] = i;
                maxi[i + n - 1] = i;
            }
            for (int i = 0; i < size; i++) {
                update(i, 0);
            }
        }

        SegmentAdd(int[] a) {
            this(a.length);
            for (int i = 0; i < a.length; i++) {
                update(i, a[i]);
            }
        }

        SegmentAdd(long[] a) {
            this(a.length);
            for (int i = 0; i < a.length; i++) {
                update(i, a[i]);
            }
        }

        public void update(int i, long x) {
            i += n - 1;
            sum[i] = x;
            min[i] = x;
            max[i] = x;
            while (i > 0) {
                i = (i - 1) / 2;
                sum[i] = sum[i * 2 + 1] + sum[i * 2 + 2];
                setMinMax(i);
            }
        }

        public void add(int l, int r, long x) {
            add(l, r, 0, x, 0, n);
        }

        public void add(int a, int b, int k, long x, int l, int r) {
            eval(k, l, r);
            if (r <= a || b <= l) return;
            else if (a <= l && r <= b) {
                lazy[k] += x;
                eval(k, l, r);
            } else {
                add(a, b, k * 2 + 1, x, l, (l + r) / 2);
                add(a, b, k * 2 + 2, x, (l + r) / 2, r);
                sum[k] = sum[k * 2 + 1] + sum[k * 2 + 2];
                setMinMax(k);
            }
        }

        public long sum(int l, int r) {
            return sum(l, r, 0, 0, n);
        }

        public long sum(int a, int b, int k, int l, int r) {
            eval(k, l, r);
            if (r <= a || b <= l) return 0;
            else if (a <= l && r <= b) {
                return sum[k];
            } else {
                long lv = sum(a, b, k * 2 + 1, l, (l + r) / 2);
                long rv = sum(a, b, k * 2 + 2, (l + r) / 2, r);
                return lv + rv;
            }
        }

        public long min(int l, int r) {
            return min(l, r, 0, 0, n);
        }

        public long min(int a, int b, int k, int l, int r) {
            eval(k, l, r);
            if (r <= a || b <= l) return Integer.MAX_VALUE;
            else if (a <= l && r <= b) {
                return min[k];
            } else {
                long lv = min(a, b, k * 2 + 1, l, (l + r) / 2);
                long rv = min(a, b, k * 2 + 2, (l + r) / 2, r);
                return Math.min(lv, rv);
            }
        }

        public int mini(int l, int r) {
            return mini(l, r, 0, 0, n);
        }

        public int mini(int a, int b, int k, int l, int r) {
            eval(k, l, r);
            if (r <= a || b <= l) return -1;
            else if (a <= l && r <= b) {
                return mini[k];
            } else {
                long lv = min(a, b, k * 2 + 1, l, (l + r) / 2);
                long rv = min(a, b, k * 2 + 2, (l + r) / 2, r);
                int li = mini(a, b, k * 2 + 1, l, (l + r) / 2);
                int ri = mini(a, b, k * 2 + 2, (l + r) / 2, r);
                return lv < rv ? li : ri;
            }
        }

        public long max(int l, int r) {
            return max(l, r, 0, 0, n);
        }

        public long max(int a, int b, int k, int l, int r) {
            eval(k, l, r);
            if (r <= a || b <= l) return Integer.MIN_VALUE;
            else if (a <= l && r <= b) {
                return max[k];
            } else {
                long lv = max(a, b, k * 2 + 1, l, (l + r) / 2);
                long rv = max(a, b, k * 2 + 2, (l + r) / 2, r);
                return Math.max(lv, rv);
            }
        }

        public int maxi(int l, int r) {
            return maxi(l, r, 0, 0, n);
        }

        public int maxi(int a, int b, int k, int l, int r) {
            eval(k, l, r);
            if (r <= a || b <= l) return -1;
            else if (a <= l && r <= b) {
                return maxi[k];
            } else {
                long lv = max(a, b, k * 2 + 1, l, (l + r) / 2);
                long rv = max(a, b, k * 2 + 2, (l + r) / 2, r);
                int li = maxi(a, b, k * 2 + 1, l, (l + r) / 2);
                int ri = maxi(a, b, k * 2 + 2, (l + r) / 2, r);
                return lv > rv ? li : ri;
            }
        }


        private void eval(int k, int l, int r) {
            if (lazy[k] != 0) {
                sum[k] += lazy[k] * (r - l);
                min[k] += lazy[k];
                max[k] += lazy[k];
                if (r - l > 1) {
                    lazy[k * 2 + 1] += lazy[k];
                    lazy[k * 2 + 2] += lazy[k];
                }
                lazy[k] = 0;
            }
        }

        private void setMinMax(int i) {
            if (min[i * 2 + 1] <= min[i * 2 + 2]) {
                min[i] = min[i * 2 + 1];
                mini[i] = mini[i * 2 + 1];
            } else {
                min[i] = min[i * 2 + 2];
                mini[i] = mini[i * 2 + 2];
            }
            if (max[i * 2 + 1] >= max[i * 2 + 2]) {
                max[i] = max[i * 2 + 1];
                maxi[i] = maxi[i * 2 + 1];
            } else {
                max[i] = max[i * 2 + 2];
                maxi[i] = maxi[i * 2 + 2];
            }
        }

    }