結果

問題 No.789 範囲の合計
ユーザー norioc
提出日時 2025-03-10 03:09:14
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 276 ms / 1,000 ms
コード長 3,618 bytes
コンパイル時間 1,171 ms
コンパイル使用メモリ 112,024 KB
実行使用メモリ 50,152 KB
最終ジャッジ日時 2025-03-10 03:09:25
合計ジャッジ時間 5,086 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

public class Compression
{
    public int n;
    public Dictionary<int, int> v2i;

    public Compression(IEnumerable<int> iterable)
    {
        var sorted = iterable.ToList();
        sorted.Sort();
        n = sorted.Count;
        v2i = new Dictionary<int, int>();
        for (int i = 0; i < sorted.Count; i++)
        {
            v2i[sorted[i]] = i;
        }
    }

    public int Count => n;

    // val のインデックスを返す
    public int Index(int val)
    {
        return v2i[val];
    }
}

public class FenwickTree
{
    public long[] data;
    public int n;

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

    // 0-indexed の位置 p に x を加算
    public void Add(int p, int x)
    {
        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;
    }
}

public class Program
{
    public static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        var queries = new List<(int type, int a, int b)>();
        var inds = new HashSet<int>();

        // 入力の読み込み
        for (int i = 0; i < N; i++)
        {
            string[] parts = Console.ReadLine().Split();
            int type = int.Parse(parts[0]);
            if (type == 0)
            {
                // a[x] += y のクエリ: 入力値を 0-indexed に変換
                int x = int.Parse(parts[1]) - 1;
                int y = int.Parse(parts[2]);
                queries.Add((0, x, y));
                inds.Add(x);
            }
            else if (type == 1)
            {
                // 区間 [l, r] の和を求めるクエリ: 0-indexed に変換
                int l = int.Parse(parts[1]) - 1;
                int r = int.Parse(parts[2]) - 1;
                queries.Add((1, l, r));
                inds.Add(l);
                inds.Add(r);
            }
        }

        // インデックス圧縮：重複のない値をソートして 0-indexed の番号を割り当てる
        var sortedInds = inds.ToList();
        sortedInds.Sort();
        var v2i = new Dictionary<int, int>();
        for (int i = 0; i < sortedInds.Count; i++)
        {
            v2i[sortedInds[i]] = i;
        }

        // FenwickTree の初期化（サイズは v2i の要素数 + 10）
        FenwickTree ft = new FenwickTree(sortedInds.Count + 10);

        long ans = 0;
        // クエリの処理
        foreach (var q in queries)
        {
            if (q.type == 0)
            {
                int x = q.a;
                int y = q.b;
                int p = v2i[x];
                ft.Add(p, y);
            }
            else if (q.type == 1)
            {
                int l = q.a;
                int r = q.b;
                int li = v2i[l];
                int ri = v2i[r];
                long res = ft.RangeSum(li, ri);
                ans += res;
            }
        }

        Console.WriteLine(ans);
    }
}
0