Submission #73369335

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <deque>
#include <queue>
#include <unordered_map>
#include <string>
#include <map>
#include <cmath>
# include <iomanip>
#include <numeric>
#include <unordered_set>
#include <bitset>
#include <functional>
#include <cassert>
/*
* 優先度付きキュー（先頭が小さい値になる.計算量はlogN）
priority_queue<int, vector<int>, greater<int>> pq;
*/
using namespace std;
int INF = 100000000;


template<typename T>
class segmenttree {

private:
    int n;
    int size_;
    std::vector<T> dat;
    std::function<T(T, T)> calc;
    T id;

public:

    void init(int N, std::function<T(T, T)> func, T e) {
        size_ = N;
        n = 1;
        while (n < N)n <<= 1;
        calc = func;
        id = e;
        dat.assign(2 * n - 1, e);
    }

    void init(std::vector<T> a, std::function<T(T, T)> func, T e) {
        init(a.size(), func, e);
        set(a);
    }

    segmenttree(int N, std::function<T(T, T)> func, T e) {
        init(N, func, e);
    }

    segmenttree(std::vector<T> a, std::function<T(T, T)> func, T e) {
        init(a, func, e);
    }

    void set(int k, T a) {
        assert(0 <= k && k < size_);
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = calc(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }

    void set(std::vector<T> a) {
        assert((int)a.size() == size_);
        dat.assign(2 * n - 1, id);
        for (int k = 0; k < size_; k++) {
            dat[n + k - 1] = a[k];
        }
        for (int k = n - 2; k >= 0; k--) {
            dat[k] = calc(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }

    T prod(int a, int b) {
        assert(0 <= a && a <= b && b <= size_);
        a += n - 1;
        b += n - 1;
        T L = id, R = id;
        while (a < b) {
            if (a % 2 == 0) {
                L = calc(L, dat[a]);
                a++;
            }
            a = (a - 1) / 2;
            if (b % 2 == 0) {
                b--;
                R = calc(dat[b], R);
            }
            b = (b - 1) / 2;
        }
        return calc(L, R);
    }
};





int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long>A(N);
    for (int i = 0; i < N; i++)cin >> A[i];

    function<long long(long long, long long)> func = [](long long a, long long b) {
        return a + b;
    };

    segmenttree<long long> segtree(A, func, 0);

    for (int i = 0; i < Q; i++) {
        int a;
        cin >> a;
        if (a == 1) {
            int l, r;
            cin >> l >> r;
            l--;
            cout << segtree.prod(l, r) << endl;
        }
        else {
            int x, v;
            cin >> x >> v;
            x--;
            segtree.set(x, v);
        }
    }

}

Submission Info

Judge Result