Submission #52722

ソースコード

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)
 
using i64 = long long;
using pii = pair<i64, i64>;
 
template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}
 
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;
 
template<typename Monoid> struct SegmentTree {
  using Func = function<Monoid(Monoid, Monoid)>;
  const i64 sz;
  const Func fn;
  const Monoid unity;
  vector<Monoid> seg;
 
  SegmentTree(i64 n, const Monoid &u, Func f)
    : sz(1 << (__lg(n + 5) + 1)), fn(f), unity(u), seg(sz * 2, unity) {}
 
  void set(i64 k, const Monoid &v) { seg[k+sz] = v; }
 
  Monoid& operator[](i64 k) { return seg[k+sz]; }
  const Monoid& operator[](i64 k) const { return seg[k+sz]; }
 
  void build() { for (i64 k = sz - 1; k > 0; --k) seg[k] = fn(seg[2*k], seg[2*k+1]); }
 
  void update(i64 k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) seg[k] = fn(seg[2*k], seg[2*k+1]);
  }
 
  Monoid query(i64 a, i64 b) const {
    Monoid L = unity, R = unity;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = fn(L, seg[a++]);
      if (b & 1) R = fn(seg[--b], R);
    }
    return fn(L, R);
  }
};
 
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int N, M;
  cin >> N >> M;
 
  SegmentTree<i64> minseg(N, LINF, [](int a, int b) { return min(a, b); });
  SegmentTree<i64> maxseg(N, -LINF, [](int a, int b) { return max(a, b); });
  SegmentTree<i64> sumseg(N, 0, [](int a, int b) { return a + b; });
 
  rep(i, N) minseg[i] = maxseg[i] = 0;
 
  minseg.build();
  maxseg.build();
 
  string q;
  i64 a, b;
  rep(i, M) {
    cin >> q >> a >> b;
 
    if (q == "update") {
      minseg.update(a, b);
      maxseg.update(a, b);
      sumseg.update(a, b);
    }
 
    else if (q == "add") {
      minseg.update(a, minseg[a] + b);
      maxseg.update(a, maxseg[a] + b);
      sumseg.update(a, sumseg[a] + b);
    }
 
    else if (q == "getMin") cout << minseg.query(a, b) << "\n";
 
    else if (q == "getMax") cout << maxseg.query(a, b) << "\n";
 
    else cout << sumseg.query(a, b) << "\n";
  }
 
  return 0;
}

ステータス

項目	データ
問題	1072 - セグメントツリー技術基礎
ユーザー名	もけ
投稿日時	2019-08-10 16:56:28
言語	C++14
状態	Accepted
得点	1
ソースコード長	2450 Byte
最大実行時間	62 ms
最大メモリ使用量	12092 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01	AC	28 ms	604 KB	1
in02	AC	46 ms	816 KB	1
in03	AC	44 ms	6972 KB	1
in04	AC	50 ms	7288 KB	1
in05	AC	27 ms	7352 KB	1
in06	AC	34 ms	4340 KB	1
in07	AC	39 ms	4528 KB	1
in08	AC	45 ms	3308 KB	1
in09	AC	58 ms	7980 KB	1
in10	AC	53 ms	5356 KB	1
in11	AC	30 ms	3760 KB	1
in12	AC	32 ms	2544 KB	1
in13	AC	55 ms	8700 KB	1
in14	AC	52 ms	4408 KB	1
in15	AC	42 ms	9212 KB	1
in16	AC	43 ms	4028 KB	1
in17	AC	42 ms	9720 KB	1
in18	AC	37 ms	9656 KB	1
in19	AC	54 ms	9852 KB	1
in20	AC	31 ms	9916 KB	1
in21	AC	43 ms	7036 KB	1
in22	AC	56 ms	7352 KB	1
in23	AC	40 ms	10620 KB	1
in24	AC	53 ms	7740 KB	1
in25	AC	44 ms	6524 KB	1
in26	AC	53 ms	11324 KB	1
in27	AC	51 ms	11512 KB	1
in28	AC	62 ms	8764 KB	1
in29	AC	36 ms	11896 KB	1
in30	AC	49 ms	12092 KB	1
in31	AC	37 ms	9340 KB	1
in32	AC	49 ms	9532 KB	1