#1175311 (C++23(gnu拡張gcc16)) No.3614 Breaking door keys（LITTLE BREAK ver.）

• 問題: No.3614 Breaking door keys（LITTLE BREAK ver.）
• ユーザー: KEYBO
• 提出日時: 2026-08-06 14:52:28
• 言語: C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 756 ms / 2,000 ms
• コード長: 2,853 bytes
• コンパイル時間: 5,645 ms
• コンパイル使用メモリ: 392,800 KB
• 実行使用メモリ: 29,312 KB
• 最終ジャッジ日時: 2026-08-06 14:52:56
• 合計ジャッジ時間: 20,731 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

サブタスク	配点	結果
サンプル	0 %	AC * 3
小課題1	10 %	AC * 7
小課題2	20 %	AC * 7
小課題3	30 %	AC * 7
小課題4	30 %	AC * 14
小課題5	10 %	AC * 38
合計	2.5 * 100% = 250 点

ソースコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

using ll = int64_t;
using ul = uint64_t;
using ld = long double;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vs = vector<string>;
using vb = vector<bool>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvd = vector<vd>;
using vvc = vector<vc>;
using vvb = vector<vb>;
using vvl = vector<vl>;
using mint = modint998244353;
using vm = vector<mint>;

template <typename X>
struct SegTree {
  using FX = function<X(X, X)>; // X○X -> Xとなる関数の型
  int N; // 葉の数
  FX fx; // 関数
  const X ex; // 単位元
  vector<X> data; // セグ木

  // 初期化
  SegTree(int N_, FX fx_, X ex_) : N(), fx(fx_), ex(ex_), data(N_*4, ex_) {
    int x = 1;
    while(N_ > x) x *= 2;
    N = x;
  }
  // 0 <= pos <= N - 1
  void set(int pos, X x) {
    data[pos + N - 1] = x;
    return;
  }
  void build() {
    for (int pos = N - 2; pos >= 0; pos--) {
      data[pos] = fx(data[pos*2 + 1], data[pos*2 + 2]);
    }
    return;
  }

  // 1点更新
  // 0 <= pos <= N - 1
  void update(int pos, X x) {
    pos += N - 1;
    data[pos] = x;
    while(pos > 0) {
      pos = (pos - 1)/2; // 親へ伝播
      data[pos] = fx(data[pos*2 + 1], data[pos*2 + 2]);
    }
    return;
  }

  // クエリ呼び出し
  // 0 <= a <= N - 1
  // 1 <= b <= N
  X query(int a, int b) {
    return query_sub(a, b, 0, 0, N);
  }

  // クエリ回答
  X query_sub(int a, int b, int pos, int l, int r) {
    // 範囲外
    if (r <= a || b <= l) {
      return ex;
    }
    // 完全に含まれる
    else if (a <= l && r <= b) {
      return data[pos];
    }
    // 一部だけ含まれる
    else {
      X L = query_sub(a, b, pos*2 + 1, l, (l + r)/2);
      X R = query_sub(a, b, pos*2 + 2, (l + r)/2, r);
      return fx(L, R);
    }
  }
};

int main() {
  int N,Q;
  cin >> N >> Q;
  vl S(N);
  for (int i = 0; i < N; i++) {
    cin >> S[i];
  }
  auto fx = [](vl x1, vl x2) -> vl {
    vl res;
    int l = 0,r = 0,cnt = 0;
    while(cnt < 10 && (l < x1.size() || r < x2.size())) {
      if (l >= x1.size()) {
        res.push_back(x2[r]);
        r++;
      }
      else if (r >= x2.size()) {
        res.push_back(x1[l]);
        l++;
      }
      else if (x1[l] < x2[r]) {
        res.push_back(x1[l]);
        l++;
      }
      else {
        res.push_back(x2[r]);
        r++;
      }
      cnt++;
    }
    return res;
  };
  vl ex = {1000000000000000000};
  SegTree<vl> seg(N, fx, ex);
  for (int i = 0; i < N; i++) {
    vl dat = {S[i]};
    seg.set(i, dat);
  }
  seg.build();
  for (int i = 0; i < Q; i++) {
    int L,R,K;
    cin >> L >> R >> K;
    L--;
    vl Min = seg.query(L, R);
    ll ans = 0;
    for (int j = 0; j < K; j++) {
      ans += Min[j];
    }
    cout << ans << endl;
  }
  return 0;
}