結果

問題 No.789 範囲の合計
コンテスト
ユーザー norioc
提出日時 2025-03-10 03:01:25
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 4,259 bytes
コンパイル時間 2,909 ms
コンパイル使用メモリ 83,356 KB
実行使用メモリ 93,372 KB
最終ジャッジ日時 2025-03-10 03:01:45
合計ジャッジ時間 18,715 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

public class Main {

    // 圧縮クラス（必要なら利用できますが、ここでは直接マッピングを作成しています）
    static class Compression {
        int n;
        Map<Integer, Integer> v2i;

        public Compression(Collection<Integer> iterable) {
            n = iterable.size();
            v2i = new HashMap<>();
            List<Integer> sorted = new ArrayList<>(iterable);
            Collections.sort(sorted);
            for (int i = 0; i < sorted.size(); i++) {
                v2i.put(sorted.get(i), i);
            }
        }

        public int size() {
            return n;
        }

        // val のインデックスを返す
        public int index(int val) {
            return v2i.get(val);
        }
    }

    // FenwickTree (Binary Indexed Tree) クラス
    static class FenwickTree {
        long[] data;
        int n;

        // コンストラクタ：内部でサイズを n+10 として確保
        public FenwickTree(int n) {
            this.n = n + 10;
            data = new long[this.n];
        }

        // 点 p に x を加算 (p は 0-indexed)
        public void add(int p, int x) {
            // 0 <= p < n の前提
            p++; // 1-indexed に変換
            while (p < data.length) {
                data[p] += x;
                p += p & -p;
            }
        }

        // 区間 [0, p] の和 (p は 0-indexed)
        public long sum(int p) {
            p++; // 1-indexed に変換
            long s = 0;
            while (p > 0) {
                s += data[p];
                p -= p & -p;
            }
            return s;
        }

        // 区間 [l, r] の和 (l, r は 0-indexed)
        public long rangesum(int l, int r) {
            long s = sum(r);
            if (l > 0) {
                s -= sum(l - 1);
            }
            return s;
        }
    }

    // クエリを表すクラス
    static class Query {
        int type; // 0: update, 1: range query
        int a, b; // update の場合: a = x, b = y; range query の場合: a = l, b = r

        public Query(int type, int a, int b) {
            this.type = type;
            this.a = a;
            this.b = b;
        }
    }

    public static void main(String[] args) throws Exception {
        // 入力の読み込み
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Query[] queries = new Query[N];
        // インデックス圧縮用に使用する値をセットで収集
        Set<Integer> inds = new HashSet<>();
        for (int i = 0; i < N; i++) {
            int type = sc.nextInt();
            if (type == 0) { // a[x] += y
                int x = sc.nextInt() - 1;
                int y = sc.nextInt();
                queries[i] = new Query(0, x, y);
                inds.add(x);
            } else if (type == 1) { // 区間 [l, r] の和を求める
                int l = sc.nextInt() - 1;
                int r = sc.nextInt() - 1;
                queries[i] = new Query(1, l, r);
                inds.add(l);
                inds.add(r);
            }
        }

        // インデックス圧縮：inds をソートして、それぞれの値に対して 0-indexed の番号を割り当てる
        List<Integer> sortedList = new ArrayList<>(inds);
        Collections.sort(sortedList);
        Map<Integer, Integer> v2i = new HashMap<>();
        for (int i = 0; i < sortedList.size(); i++) {
            v2i.put(sortedList.get(i), i);
        }

        // FenwickTree の初期化（サイズは v2i.size() + 10）
        FenwickTree ft = new FenwickTree(v2i.size() + 10);

        long ans = 0;
        for (int i = 0; i < N; i++) {
            Query q = queries[i];
            if (q.type == 0) {
                int x = q.a;
                int y = q.b;
                int p = v2i.get(x);
                ft.add(p, y);
            } else if (q.type == 1) {
                int l = q.a;
                int r = q.b;
                int li = v2i.get(l);
                int ri = v2i.get(r);
                long res = ft.rangesum(li, ri);
                ans += res;
            }
        }
        System.out.println(ans);
        sc.close();
    }
}
0