Submission #70974206

---

Source Code Expand

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

public class Main {

    static final int MAX_VAL = 500000;
    static final int BIT_SIZE = MAX_VAL + 2;

    static long[] countBIT = new long[BIT_SIZE];
    static long[] sumBIT = new long[BIT_SIZE];

    static int[] A;
    static int N; 

    static void update(int value, int count_delta, long sum_delta) {
        int idx = value + 1;
        while (idx < BIT_SIZE) {
            countBIT[idx] += count_delta;
            sumBIT[idx] += sum_delta;
            idx += idx & (-idx); 
        }
    }

    static long query_count(int value) {
        int idx = value + 1; 
        long count = 0;
        while (idx > 0) {
            count += countBIT[idx];
            idx -= idx & (-idx); 
        }
        return count;
    }

    static long query_sum(int value) {
        int idx = value + 1; 
        long sum = 0;
        while (idx > 0) {
            sum += sumBIT[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        A = new int[N];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            update(A[i], 1, A[i]);
        }

        for (int q = 0; q < Q; q++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());

            if (type == 1) {
                int x = Integer.parseInt(st.nextToken()) - 1; 
                int y = Integer.parseInt(st.nextToken());
                
                update(A[x], -1, -A[x]);
                
                update(y, 1, y);
                
                A[x] = y;

            } else {
                int l = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());

                //
                // Handle the case where l > r
                // max(l, min(r, A_i)) will always be 'l' if l > r.
                // So the sum is just N * l.
                if (l > r) {
                    pw.println((long)N * l);
                } else {
                    long totalSum = 0;

                    long count_less_l = query_count(l - 1);
                    totalSum += count_less_l * l;

                    long sum_in_range = query_sum(r) - query_sum(l - 1);
                    totalSum += sum_in_range;

                    long count_greater_r = N - query_count(r);
                    totalSum += count_greater_r * r;

                    pw.println(totalSum);
                }
            }
        }

        pw.flush();
        pw.close();
        br.close();
    }
}

Submission Info

Judge Result