Submission #52733

ソースコード

#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;
    ios::sync_with_stdio(false);
    cin.tie(0);
    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:53:17
言語	C++14
状態	Accepted
得点	1
ソースコード長	2074 Byte
最大実行時間	162 ms
最大メモリ使用量	12340 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01	AC	22 ms	600 KB	1
in02	AC	109 ms	1068 KB	1
in03	AC	87 ms	6968 KB	1
in04	AC	150 ms	7288 KB	1
in05	AC	38 ms	7352 KB	1
in06	AC	69 ms	4348 KB	1
in07	AC	79 ms	4676 KB	1
in08	AC	134 ms	3212 KB	1
in09	AC	111 ms	8148 KB	1
in10	AC	145 ms	5268 KB	1
in11	AC	39 ms	3676 KB	1
in12	AC	68 ms	2460 KB	1
in13	AC	119 ms	8752 KB	1
in14	AC	148 ms	4344 KB	1
in15	AC	85 ms	9280 KB	1
in16	AC	118 ms	4096 KB	1
in17	AC	125 ms	9668 KB	1
in18	AC	66 ms	9864 KB	1
in19	AC	122 ms	10056 KB	1
in20	AC	66 ms	10128 KB	1
in21	AC	83 ms	7124 KB	1
in22	AC	139 ms	7452 KB	1
in23	AC	101 ms	10720 KB	1
in24	AC	112 ms	7836 KB	1
in25	AC	121 ms	6500 KB	1
in26	AC	132 ms	11432 KB	1
in27	AC	122 ms	11628 KB	1
in28	AC	162 ms	8748 KB	1
in29	AC	53 ms	11884 KB	1
in30	AC	128 ms	12340 KB	1
in31	AC	79 ms	9464 KB	1
in32	AC	117 ms	9788 KB	1