#377420 (Java21) No.876 Range Compress Query

• 問題: No.876 Range Compress Query
• ユーザー: kusomushi
• 提出日時: 2019-09-08 05:35:25
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 634 ms / 2,000 ms
• コード長: 11,774 bytes
• コンパイル時間: 2,778 ms
• コンパイル使用メモリ: 87,864 KB
• 実行使用メモリ: 52,116 KB
• 最終ジャッジ日時: 2024-06-27 14:51:27
• 合計ジャッジ時間: 9,663 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	54 ms; 37,012 KB
testcase_01	AC	88 ms; 38,568 KB
testcase_02	AC	55 ms; 37,068 KB
testcase_03	AC	90 ms; 38,784 KB
testcase_04	AC	65 ms; 37,272 KB
testcase_05	AC	60 ms; 37,400 KB
testcase_06	AC	100 ms; 38,664 KB
testcase_07	AC	86 ms; 38,520 KB
testcase_08	AC	97 ms; 38,832 KB
testcase_09	AC	89 ms; 38,324 KB
testcase_10	AC	92 ms; 38,524 KB
testcase_11	AC	582 ms; 51,360 KB
testcase_12	AC	506 ms; 49,944 KB
testcase_13	AC	551 ms; 50,516 KB
testcase_14	AC	556 ms; 50,032 KB
testcase_15	AC	523 ms; 52,012 KB
testcase_16	AC	576 ms; 50,988 KB
testcase_17	AC	612 ms; 52,116 KB
testcase_18	AC	634 ms; 52,080 KB

ソースコード

import java.io.*;
import java.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.function.Function;

public class Main {

    static int N, Q;
    static int[] A;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        N = sc.nextInt();
        Q = sc.nextInt();
        A = sc.nextIntArray(N);

        FenwickTree between = new FenwickTree(N-1, FenwickTree.SUM);
        RangeUpdate seg = new RangeUpdate(N, RangeUpdate.ADD);
        for (int i = 0; i < N; i++) {
            if( i != N-1 && A[i] != A[i+1] ) {
                between.add(i, 1);
            }
            seg.update(i, i+1, A[i]);
        }

        for (int q = 0; q < Q; q++) {
            int type = sc.nextInt();
            if( type == 1 ) {
                int l = sc.nextInt()-1;
                int r = sc.nextInt()-1;
                int v = sc.nextInt();

                // [l, r]をv増やす
                // -> between(l-1, l)とbetween(r, r+1)が変化する
                if( l != 0 ) {
                    long prev = seg.get(l-1);
                    long left = seg.get(l);
                    if( prev == left ) {
                        // 切れる
                        between.add(l-1, 1);
                    }
                }
                if( r != N-1 ) {
                    if( seg.get(r) == seg.get(r+1) ) {
                        // 切れる
                        between.add(r, 1);
                    }
                }

                seg.update(l, r+1, v);

                if( l != 0 ) {
                    long prev = seg.get(l-1);
                    long left = seg.get(l);
                    if( prev == left ) {
                        // つながった
                        between.add(l-1, -1);
                    }
                }
                if( r != N-1 ) {
                    if( seg.get(r) == seg.get(r+1) ) {
                        // つながった
                        between.add(r, -1);
                    }
                }


            } else {
                int l = sc.nextInt()-1;
                int r = sc.nextInt()-1;
                int bet = (int)between.query(l, r); // [l, r] -> between[l, r-1] -> between[l, r)
                pw.println(bet+1);
            }
        }

        pw.flush();
    }

    static class FenwickTree {

        interface Monoid {
            long identity();
            long apply(long a, long b);
            long inverse(long a);
        }

        static Monoid SUM = new Monoid() {
            public long identity() { return 0; }
            public long apply(long a, long b) { return a+b; }
            public long inverse(long a) { return -a; }
        };

        static Monoid MAX = new Monoid() {
            public long identity() { return 0; }
            public long apply(long a, long b) { return Math.max(a, b); }
            public long inverse(long a) { throw new RuntimeException("no inverse"); }
        };


        int size;
        long[] bit;
        Monoid m;
        long identity;

        FenwickTree(int size, Monoid m) {
            this.size = 1;
            while( this.size < size ) this.size *= 2;
            this.bit = new long[this.size+1];
            this.identity = m.identity();
            if( this.identity != 0 ) {
                Arrays.fill(this.bit, this.identity);
            }
            this.m = m;
        }

        void add(int i, long v) {
            i++; // 0 index -> 1 index

            while( i <= size ) {
                bit[i] = m.apply(bit[i], v);
                i += i & -i;
            }
        }

        // [0, r)
        long query(int r) {
            // 0 index -> 1 index -> -1
            long ret = identity;
            while(r > 0) {
                ret = m.apply(ret, bit[r]);
                r -= r & -r;
            }
            return ret;
        }

        long query(int l, int r) {
            return query(r) + m.inverse(query(l));
        }

        int lowerBound(int v) {
            if( bit[size] < v ) return size;

            int x = 0;
            for (int k = size/2; k > 0; k /= 2 ) {
                if( bit[x + k] < v ) {
                    v -= bit[x+k];
                    x += k;
                }
            }
            return x;
        }
    }

    static class RangeGet {

        interface Monoid {
            long identity();
            long apply(long a, long b);
        }

        static Monoid MOD_SUM(int mod) {
            return new Monoid() {
                public long identity() { return 0; }
                public long apply(long a, long b) {
                    long c = a + b;
                    if( c >= mod ) {
                        c %= mod;
                    }
                    return c;
                }
            };
        }

        static Monoid SUM = new Monoid() {
            public long identity() { return 0; }
            public long apply(long a, long b) { return a + b; }
        };

        static Monoid MAX = new Monoid() {
            public long identity() { return Long.MIN_VALUE / 2; }
            public long apply(long a, long b) { return Math.max(a, b); }
        };

        static Monoid MIN = new Monoid() {
            public long identity() { return Long.MAX_VALUE / 2; }
            public long apply(long a, long b) { return Math.min(a, b); }
        };

        int size;
        long[] tree;
        Monoid m;
        long identity;

        RangeGet(int size, Monoid m) {
            this.size = 1;
            while( this.size < size ) this.size *= 2;
            this.tree = new long[this.size*2];
            this.m = m;
            this.identity = m.identity();
            if( this.identity != 0 ) {
                Arrays.fill(this.tree, this.identity);
            }
        }

        void update(int idx, long v) {
            idx += size;
            tree[idx] = v;

            while(idx > 0) {
                idx /= 2;
                tree[idx] = m.apply(tree[idx*2], tree[idx*2+1]);
            }
        }

        // [from, to)
        long query(int from, int to) {
            return _query(from, to, 1, 0, size);
        }

        private long _query(int from, int to, int idx, int l, int r) {
            if (r <= from || to <= l) return identity;

            if (from <= l && r <= to) {
                return tree[idx];

            } else {
                int mid = (l+r)/2;
                long vl = _query(from, to, idx*2, l, mid);
                long vr = _query(from, to, idx*2+1, mid, r);
                return m.apply(vl, vr);
            }
        }

        long get(int idx) {
            return tree[idx+size];
        }
    }

    static class RangeUpdate {
        interface Monoid {
            long identity();
            long apply(long a, long b);
        }

        static Monoid ADD = new Monoid() {
            public long identity() { return 0; }
            public long apply(long a, long b) { return a + b; }
        };

        static Monoid MAX = new Monoid() {
            public long identity() { return Long.MIN_VALUE / 2; }
            public long apply(long a, long b) { return Math.max(a, b); }
        };

        static Monoid MIN = new Monoid() {
            public long identity() { return Long.MAX_VALUE / 2; }
            public long apply(long a, long b) { return Math.min(a, b); }
        };

        int size;
        long[] tree;
        Monoid m;
        long identity;

        RangeUpdate(int size, Monoid m) {
            this.size = 1;
            while( this.size < size ) this.size *= 2;
            this.tree = new long[this.size*2];
            this.m = m;
            this.identity = m.identity();
            if( this.identity != 0 ) {
                Arrays.fill(this.tree, this.identity);
            }
        }

        // [from, to)
        void update(int from, int to, long v) {
            _update(from, to, 1, 0, size, v);
        }

        void _update(int from, int to, int idx, int l, int r, long v) {
            if (from <= l && r <= to) {
                tree[idx] = m.apply(tree[idx], v);
                return;
            }

            int mid = (l+r)/2;
            if (from < mid) _update(from, to, idx*2, l, mid, v);
            if (mid < to) _update(from, to, idx*2+1, mid, r, v);
        }

        long get(int idx) {
            long ret = identity;
            idx += size;
            while( idx > 0 ) {
                ret = m.apply(tree[idx], ret);
                idx /= 2;
            }
            return ret;
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }

    static <A> void writeLines(A[] as, Function<A, String> f) {
        PrintWriter pw = new PrintWriter(System.out);
        for (A a : as) {
            pw.println(f.apply(a));
        }
        pw.flush();
    }

    static void writeLines(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (long a : as) pw.println(a);
        pw.flush();
    }

    static int max(int... as) {
        int max = Integer.MIN_VALUE;
        for (int a : as) max = Math.max(a, max);
        return max;
    }

    static int min(int... as) {
        int min = Integer.MAX_VALUE;
        for (int a : as) min = Math.min(a, min);
        return min;
    }

    static void debug(Object... args) {
        StringJoiner j = new StringJoiner(" ");
        for (Object arg : args) {
            if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }
}