src/test/aoj_DSL_2_B.cpp

• View this file on GitHub
• Last update: 2025-10-08 00:44:44+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

• src/fenwick_tree.hpp
• src/template.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#include "../fenwick_tree.hpp"

int main() {
    int n, q;
    cin >> n >> q;
    fenwick_tree<int> bit(n);
    rep(i, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if(c == 0) {
            bit.add(x-1, y);
        }
        else {
            cout << bit.sum(x-1, y) << "\n";
        }
    }
}

#line 1 "src/test/aoj_DSL_2_B.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/fenwick_tree.hpp"

template<class T> struct fenwick_tree {
    vector<T> a;
    fenwick_tree(): a(1) {}
    fenwick_tree(int n): a(n + 1) {}
    void add(int i, T x) {
        i++;
        while(i < si(a)) a[i] += x, i += i & -i;
    }
    T sum(int r) {
        T s = 0;
        while(r) s += a[r], r -= r & -r;
        return s;
    }
    T sum(int l, int r) { return sum(r) - sum(l); }

    //sum(0,x+1)がw以上になるような最小のxを返す(各要素は正の数)
    int lower_bound(T w) {
        if(w <= 0) return 0;
        int x = 0, N = si(a) - 1;
        for(int k = 1 << __lg(N); k >>= 1;) {
            if(x + k <= N - 1 && a[x + k] < w) {
                w -= a[x + k];
                x += k;
            }
        }
        return x;
    }
};
#line 4 "src/test/aoj_DSL_2_B.cpp"

int main() {
    int n, q;
    cin >> n >> q;
    fenwick_tree<int> bit(n);
    rep(i, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if(c == 0) {
            bit.add(x-1, y);
        }
        else {
            cout << bit.sum(x-1, y) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	5 ms	4 MB
g++	00_small_01.in	AC	4 ms	4 MB
g++	00_small_02.in	AC	4 ms	4 MB
g++	00_small_03.in	AC	4 ms	4 MB
g++	01_rand_00.in	AC	4 ms	4 MB
g++	01_rand_01.in	AC	4 ms	4 MB
g++	01_rand_02.in	AC	4 ms	4 MB
g++	01_rand_03.in	AC	4 ms	4 MB
g++	02_slight_00.in	AC	4 ms	4 MB
g++	02_slight_01.in	AC	4 ms	4 MB
g++	02_slight_02.in	AC	5 ms	4 MB
g++	02_slight_03.in	AC	8 ms	4 MB
g++	03_biased_00.in	AC	4 ms	4 MB
g++	03_biased_01.in	AC	20 ms	4 MB
g++	03_biased_02.in	AC	21 ms	4 MB
g++	03_biased_03.in	AC	20 ms	4 MB
g++	04_maximum_00.in	AC	23 ms	4 MB
g++	04_maximum_01.in	AC	23 ms	4 MB
g++	04_maximum_02.in	AC	23 ms	4 MB
g++	04_maximum_03.in	AC	23 ms	4 MB
clang++	00_small_00.in	AC	5 ms	4 MB
clang++	00_small_01.in	AC	4 ms	4 MB
clang++	00_small_02.in	AC	4 ms	4 MB
clang++	00_small_03.in	AC	4 ms	4 MB
clang++	01_rand_00.in	AC	4 ms	4 MB
clang++	01_rand_01.in	AC	4 ms	4 MB
clang++	01_rand_02.in	AC	4 ms	4 MB
clang++	01_rand_03.in	AC	4 ms	4 MB
clang++	02_slight_00.in	AC	4 ms	4 MB
clang++	02_slight_01.in	AC	4 ms	4 MB
clang++	02_slight_02.in	AC	4 ms	4 MB
clang++	02_slight_03.in	AC	8 ms	4 MB
clang++	03_biased_00.in	AC	4 ms	4 MB
clang++	03_biased_01.in	AC	20 ms	4 MB
clang++	03_biased_02.in	AC	21 ms	4 MB
clang++	03_biased_03.in	AC	20 ms	4 MB
clang++	04_maximum_00.in	AC	23 ms	4 MB
clang++	04_maximum_01.in	AC	23 ms	4 MB
clang++	04_maximum_02.in	AC	23 ms	4 MB
clang++	04_maximum_03.in	AC	23 ms	4 MB

Back to top page