結果

問題 No.2065 Sum of Min
コンテスト
ユーザー yuunegi
提出日時 2026-10-30 12:08:47
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 570 ms / 2,000 ms
+ 613µs
コード長 2,031 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,184 ms
コンパイル使用メモリ 346,852 KB
実行使用メモリ 54,360 KB
最終ジャッジ日時 2026-10-30 12:09:55
合計ジャッジ時間 20,160 ms
ジャッジサーバーID
（参考情報） 		judge7_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
struct MergeSortTree {
    int n, sz;
    bool use_sum;
    vector<vector<long long>> dat;
    vector<vector<long long>> sum;

    MergeSortTree(const vector<long long>& a,bool flag=false) {
        n = a.size();
        use_sum = flag;
        sz = 1;
        while (sz < n) sz <<= 1;
        dat.resize(2 * sz);
        if(use_sum)sum.resize(2 * sz);
        // 葉
        for (int i = 0; i < n; i++) dat[sz + i].push_back(a[i]);
        // マージ
        for (int i = sz - 1; i >= 1; i--) merge(dat[2 * i].begin(), dat[2 * i].end(),dat[2 * i + 1].begin(), dat[2 * i + 1].end(),back_inserter(dat[i]));
        // 累積和
        if(use_sum)for (int i = 1; i < 2 * sz; i++) {
            sum[i].resize(dat[i].size() + 1);
            for (int j = 0; j < (int)dat[i].size(); j++) {
                sum[i][j + 1] = sum[i][j] + dat[i][j];
            }
        }
    }
private:
    // 1ノードについて clamp(x, lo, hi) の総和
    long long node_sum_clamp(int p, long long lo, long long hi) const {
        int l = lower_bound(dat[p].begin(), dat[p].end(), lo) - dat[p].begin();
        int r = upper_bound(dat[p].begin(), dat[p].end(), hi) - dat[p].begin();
        return (long long)l * lo + (sum[p][r] - sum[p][l]) + (long long)(dat[p].size() - r) * hi;
    }
public:
    // [l,r) にある全 x について clamp(x,lo,hi) の総和
    long long sum_clamp(int l, int r, long long lo, long long hi) const {
        assert(use_sum);
        long long res = 0;
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += node_sum_clamp(l++, lo, hi);
            if (r & 1) res += node_sum_clamp(--r, lo, hi);
        }
        return res;
    }
};

int main(void){
    int n,q;
    cin>>n>>q;
    vector<long long>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    MergeSortTree mst(v,1);
    while(q--){
        int l,r;
        long long x;
        cin>>l>>r>>x;
        cout<<mst.sum_clamp(l-1,r,0,x)<<endl;
    }
    return 0;
}
0