Submission #52732

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
template <class Monoid> struct SegmentTree{
    using Func = function<Monoid(Monoid, Monoid)>;
 
    int size;
    vector<Monoid> seg;
    const Func merge;
    const Monoid def;
 
    SegmentTree(int n, Monoid d, const Func f): merge(f), def(d){
        for(size = 1; size <= n; size <<= 1);
        seg.assign(size*2, def);
    }
 
    Monoid& operator[] (int i) { return seg[i+size]; };
    void build(){ for(int i = size-1;i >= 0;i--) seg[i] = merge(seg[i*2], seg[i*2+1]); }
 
    void update(int i, Monoid val){
        seg[i += size] = val;
        while(i >>= 1) seg[i] = merge(seg[i*2], seg[i*2+1]);
    }
 
    void add(int i, Monoid val){ update(i, val+seg[i+size]); }
 
    Monoid get(int a, int b){
        Monoid l = def, r = def;
        for(a += size, b += size; a < b; a >>= 1, b >>= 1){
            if(a & 1) l = merge(l, seg[a++]);
            if(b & 1) r = merge(r, seg[--b]);
        }
        return merge(l, r);
    }
};
 
#define int long long
 
signed main(){
    int n, m;
    cin >> n >> m;
    SegmentTree<int> sum(n, 0, [](int a, int b){ return a + b;});
    SegmentTree<int> ma(n, INT_MIN, [](int a, int b){ return max(a, b);});
    SegmentTree<int> mi(n, INT_MAX, [](int a, int b){ return min(a, b);});
 
    for(int i = 0;i < n;i++){
        ma[i] = mi[i] = 0;
    }
    ma.build(); mi.build();
 
    for(int i = 0;i < m;i++){
        int a, b;
        string query;
        cin >> query >> a >> b;
        if(query == "update"){
            sum.update(a, b);
            ma.update(a, b);
            mi.update(a, b);
        }else if(query == "add"){
            sum.add(a, b);
            ma.add(a, b);
            mi.add(a, b);
        }else if(query == "getSum"){
            cout << sum.get(a, b) << endl;
        }else if(query == "getMax"){
            cout << ma.get(a, b) << endl;
        }else{
            cout << mi.get(a, b) << endl;
        }
    }
    return 0;
}

ステータス

項目	データ
問題	1072 - セグメントツリー技術基礎
ユーザー名	ei1719
投稿日時	2019-08-11 19:52:29
言語	C++14
状態	Accepted
得点	1
ソースコード長	2027 Byte
最大実行時間	188 ms
最大メモリ使用量	12268 KB

セット

	セット	得点	Cases
1	ALL	1 / 1	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01	AC	24 ms	600 KB	1
in02	AC	141 ms	1084 KB	1
in03	AC	103 ms	7140 KB	1
in04	AC	151 ms	7228 KB	1
in05	AC	47 ms	7180 KB	1
in06	AC	74 ms	4196 KB	1
in07	AC	109 ms	4536 KB	1
in08	AC	178 ms	3344 KB	1
in09	AC	157 ms	8036 KB	1
in10	AC	174 ms	5308 KB	1
in11	AC	40 ms	3736 KB	1
in12	AC	84 ms	2552 KB	1
in13	AC	143 ms	8732 KB	1
in14	AC	188 ms	4464 KB	1
in15	AC	106 ms	9160 KB	1
in16	AC	155 ms	4132 KB	1
in17	AC	135 ms	9852 KB	1
in18	AC	67 ms	9940 KB	1
in19	AC	140 ms	10020 KB	1
in20	AC	80 ms	10108 KB	1
in21	AC	108 ms	7248 KB	1
in22	AC	181 ms	7588 KB	1
in23	AC	116 ms	10748 KB	1
in24	AC	130 ms	7892 KB	1
in25	AC	148 ms	6576 KB	1
in26	AC	188 ms	11404 KB	1
in27	AC	153 ms	11620 KB	1
in28	AC	182 ms	8892 KB	1
in29	AC	59 ms	12052 KB	1
in30	AC	168 ms	12268 KB	1
in31	AC	93 ms	9412 KB	1
in32	AC	149 ms	9496 KB	1