結果

問題 No.789 範囲の合計
コンテスト
ユーザー norioc
提出日時 2025-03-10 03:28:02
言語 Java
(openjdk 23)
結果
AC  
実行時間 658 ms / 1,000 ms
コード長 7,255 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,420 ms
コンパイル使用メモリ 93,400 KB
実行使用メモリ 81,828 KB
最終ジャッジ日時 2025-03-10 03:28:14
合計ジャッジ時間 9,520 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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 {
        // 入力の読み込み
        FastScanner sc = new FastScanner();
        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();
    }


static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 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;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      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();
    }

    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();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

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

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

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }
  }
  
}
0