#568757 (Java) No.1270 Range Arrange Query

• 問題: No.1270 Range Arrange Query
• ユーザー: tsutaj
• 提出日時: 2020-10-18 17:09:43
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 3,306 ms / 7,000 ms
• コード長: 8,067 bytes
• コンパイル時間: 3,190 ms
• コンパイル使用メモリ: 89,632 KB
• 実行使用メモリ: 52,348 KB
• 最終ジャッジ日時: 2024-07-21 06:34:02
• 合計ジャッジ時間: 21,230 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 15

ソースコード

import java.util.*;
import java.io.*;

class Main {
    static final int ofs = 1;
    static int N, Q;
    static int A[];
    static long res = 0, pls = 0;
    static BIT sl, sr;
    static LazySegmentTree sa;
    static boolean state[];

    public static long calc_inv(int A[]) {
        int N = A.length;
        Integer ord[] = new Integer[N];
        for(int i=0; i<N; i++) ord[i] = i;
        Arrays.sort(ord, new Comparator<Integer>() {
                public int compare(Integer x, Integer y) {
                    if(A[x] != A[y]) return A[y] - A[x];
                    return y - x;
                }
            });

        BIT rec = new BIT(N);
        long inv = 0;
        for(int i=0; i<N; i++) {
            inv += rec.prod(0 + ofs, ord[i] + ofs);
            rec.update(ord[i] + ofs, +1);
        }
        return inv;
    }

    public static Integer[] get_mo_index(int L[], int R[]) {
        int Q = L.length;
        Integer I[] = new Integer[Q];
        for(int i=0; i<Q; i++) {
            I[i] = i;
        }

        int bucket = (int)Math.sqrt(Q) + 1;
        Arrays.sort(I, new Comparator<Integer>() {
                public int compare(Integer x, Integer y) {
                    Integer bx = L[x] / bucket, by = L[y] / bucket;
                    if(bx != by) return bx - by;
                    return R[x] - R[y];
                }
            });
        return I;
    }

    public static void add(int idx, boolean left) {
        if(left) {
            sl.update(A[idx] + ofs, -1);
            sa.update(0, A[idx], -1);
            res += sl.prod(A[idx] + 1 + ofs, N + ofs);
            res += sr.prod(0 + ofs, A[idx] + ofs);
        }
        else {
            sr.update(A[idx] + ofs, -1);
            sa.update(A[idx] + 1, N, -1);
            res += sl.prod(A[idx] + 1 + ofs, N + ofs);
            res += sr.prod(0 + ofs, A[idx] + ofs);
        }
        pls = sa.query(0, N);
    }

    public static void del(int idx, boolean left) {
        if(left) {
            sl.update(A[idx] + ofs, +1);
            sa.update(0, A[idx], +1);
            res -= sl.prod(A[idx] + 1 + ofs, N + ofs);
            res -= sr.prod(0 + ofs, A[idx] + ofs);
        }
        else {
            sr.update(A[idx] + ofs, +1);
            sa.update(A[idx] + 1, N, +1);
            res -= sl.prod(A[idx] + 1 + ofs, N + ofs);
            res -= sr.prod(0 + ofs, A[idx] + ofs);
        }
        pls = sa.query(0, N);
    }

    public static void operate(int idx, boolean left) {
        state[idx] ^= true;
        if(state[idx]) add(idx, left);
        else del(idx, left);
    }
    
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        
        N = sc.nextInt();
        Q = sc.nextInt();
        sl = new BIT(N);
        sr = new BIT(N);
        sa = new LazySegmentTree(N);
        state = new boolean[N];
        
        A = new int[N];
        for(int i=0; i<N; i++) {
            A[i] = sc.nextInt();
            A[i]--;
            state[i] = true;
        }

        int L[] = new int[Q];
        int R[] = new int[Q];        
        for(int i=0; i<Q; i++) {
            int l = sc.nextInt(); l--;
            int r = sc.nextInt();
            L[i] = l; R[i] = r;
        }

        long inv = calc_inv(A);
        res = inv;

        long ans[] = new long[Q];
        Integer I[] = get_mo_index(L, R);
        int l = 0, r = N;
        for(int i=0; i<Q; i++) {
            int id = I[i];
            while(l > L[id]) operate(--l, true);
            while(r < R[id]) operate(r++, false);
            while(l < L[id]) operate(l++, true);
            while(r > R[id]) operate(--r, false);
            ans[id] = inv - res + 1L * (R[id] - L[id]) * pls;
        }
        for(int i=0; i<Q; i++) {
            out.println(ans[i]);
        }
        out.flush();
    }
}


class LazySegmentTree {
    static int node[], lazy[];
    static boolean upd[];
    static final int INF = 1 << 28;
    static int n;
    LazySegmentTree(int n_) {
        n = 1; while(n < n_) n <<= 1;
        node = new int[2*n-1];
        lazy = new int[2*n-1];
        upd = new boolean[2*n-1];
    }

    void eval(int k, int l, int r) {
        if(!upd[k]) return;
        node[k] += lazy[k];
        if(r - l > 1) {
            lazy[2*k+1] += lazy[k];
            lazy[2*k+2] += lazy[k];
            upd[2*k+1] = upd[2*k+2] = true;
        }
        lazy[k] = 0;
        upd[k] = false;
    }

    void update(int a, int b, int x, int l, int r, int k) {
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += x;
            upd[k] = true;
            eval(k, l, r);
        }
        else {
            int mid = (l + r) / 2;
            update(a, b, x, l, mid, 2*k+1);
            update(a, b, x, mid, r, 2*k+2);
            node[k] = Math.min(node[2*k+1], node[2*k+2]);
        }
    }

    int query(int a, int b, int l, int r, int k) {
        if(b <= l || r <= a) return INF;
        eval(k, l, r);
        if(a <= l && r <= b) return node[k];
        int mid = (l + r) / 2;
        int vl = query(a, b, l, mid, 2*k+1);
        int vr = query(a, b, mid, r, 2*k+2);
        return Math.min(vl, vr);
    }

    void update(int a, int b, int x) {
        update(a, b, x, 0, n, 0);
    }

    int query(int a, int b) {
        return query(a, b, 0, n, 0);
    }
}

class BIT {
    private int[] node;
    private int N;
    public BIT(int N_) {
        node = new int[N_+1];
        N = N_;
    }

    int prod(int i) {
        int res = 0;
        while(i > 0) {
            res += node[i];
            i -= i & -i;
        }
        return res;
    }

    int prod(int l, int r) {
        r--;
        int ret_l = prod(l-1);
        int ret_r = prod(r);
        return ret_r - ret_l;
    }

    void update(int i, int x) {
        while(i <= N) {
            node[i] += x;
            i += i & -i;
        }
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}