結果
問題 | No.2065 Sum of Min |
ユーザー |
![]() |
提出日時 | 2022-09-02 22:12:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 155 ms / 2,000 ms |
コード長 | 3,090 bytes |
コンパイル時間 | 2,286 ms |
コンパイル使用メモリ | 210,896 KB |
最終ジャッジ日時 | 2025-02-07 01:22:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T, typename F>class SegmentTree {public:SegmentTree(const std::size_t size, const T identity, const F operate): identity(identity),operate(operate),nodes((1 << (32 - __builtin_clz(size))) << 1, identity) {}SegmentTree(const std::vector<T> &values, const T identity, const F operate): identity(identity),operate(operate),nodes((1 << (32 - __builtin_clz(values.size()))) << 1, identity) {std::copy(values.begin(), values.end(), nodes.begin() + size());for (std::size_t i = size() - 1; i > 0; i--) {nodes[i] = operate(nodes[i << 1], nodes[(i << 1) | 1]);}}std::size_t size() const { return nodes.size() >> 1; }void update(const std::size_t index, const T value) {assert(index < size());nodes[index + size()] = value;for (std::size_t i = (index + size()) >> 1; i > 0; i >>= 1) {nodes[i] = operate(nodes[i << 1], nodes[(i << 1) | 1]);}}T fold(const std::size_t left, const std::size_t right) const { // [left, right)assert(left < right && right <= size());T x = identity;T y = identity;for (std::size_t l = left + size(), r = right + size(); l < r; l >>= 1, r >>= 1) {if (l % 2 != 0) x = operate(x, nodes[l++]);if (r % 2 != 0) y = operate(nodes[--r], y);}return operate(x, y);}private:const T identity;const F operate;std::vector<T> nodes;};template <typename T, typename F>SegmentTree<T, F> make_segment_tree(const std::size_t size, const T identity, const F operate) {return SegmentTree<T, F>(size, identity, operate);}template <typename T, typename F>SegmentTree<T, F> make_segment_tree(const std::vector<T> &values, const T identity,const F operate) {return SegmentTree<T, F>(values, identity, operate);}int main() {cin.tie(nullptr)->sync_with_stdio(false);int N, Q;cin >> N >> Q;vector<int64_t> A(N);for (auto &&e : A) {cin >> e;}vector<tuple<int64_t, int, int>> XLR(Q);for (auto &&[x, l, r] : XLR) {cin >> l >> r >> x;l--;}vector<int> indices(Q);iota(indices.begin(), indices.end(), 0);sort(indices.begin(), indices.end(), [&XLR](const auto a, const auto b) {const auto [ax, al, ar] = XLR[a];const auto [bx, bl, br] = XLR[b];return ax > bx;});priority_queue<pair<int64_t, int>> que;for (int i = 0; i < N; i++) {que.emplace(A[i], i);}auto st1 = make_segment_tree<int64_t>(A, 0, [](const auto a, const auto b) { return a + b; });auto st2 = make_segment_tree<int64_t>(N, 0, [](const auto a, const auto b) { return a + b; });vector<int64_t> res(Q);for (const int i : indices) {const auto [x, l, r] = XLR[i];while (!que.empty() && x < que.top().first) {st1.update(que.top().second, 0);st2.update(que.top().second, 1);que.pop();}res[i] = st1.fold(l, r) + x * st2.fold(l, r);}for (const auto &e : res) {cout << e << '\n';}return 0;}