結果

問題 No.3078 Difference Sum Query
コンテスト
ユーザー GOTKAKO
提出日時 2025-03-28 22:09:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 443 ms / 2,000 ms
コード長 4,487 bytes
コンパイル時間 2,531 ms
コンパイル使用メモリ 206,624 KB
実行使用メモリ 52,412 KB
最終ジャッジ日時 2025-03-28 22:09:19
合計ジャッジ時間 12,210 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using MS = long long;
class MergeSortTree{
    //構築O(要素数log|A|) クエリO(log|A|*log要素数).
    private:
    int siz = 1;
    vector<vector<MS>> dat;
    vector<vector<long long>> sum;
    void merge(int u,int p,int q){ //昇順に並んだdat[p],dat[q]の要素をdat[u]にマージ.
        int n = dat.at(p).size(),m = dat.at(q).size();
        auto &P = dat.at(p),&Q = dat.at(q),&U = dat.at(u);
        U.resize(n+m);
        int posP = 0,posQ = 0,posU = 0;
        while(posP < n && posQ < m){
            if(P.at(posP) <= Q.at(posQ)) U.at(posU++) = P.at(posP++);
            else U.at(posU++) = Q.at(posQ++);
        }
        while(posP < n) U.at(posU++) = P.at(posP++);
        while(posQ < m) U.at(posU++) = Q.at(posQ++);
    }
    vector<int> findSegment(int l,int r){ //[l,r)のセグ木区間を返す.
        l += siz; r += siz;
        vector<int> ret;
        while(l < r){
            if(l&1) ret.push_back(l++);
            if(r&1) ret.push_back(--r);
            l >>= 1; r >>= 1; 
        }
        return ret;
    }
 
    public:
    MergeSortTree(const vector<MS> &A){ //各要素値1つ.
        int N = A.size();
        while(siz < N) siz *= 2;
        dat.resize(siz<<1); sum.resize(siz<<1);
        for(int i=0; i<N; i++) dat.at(i+siz) = {A.at(i)};
        for(int i=siz-1; i>0; i--) merge(i,i*2,i*2+1);
        for(int i=1; i<2*siz; i++){
            sum.at(i) = dat.at(i);
            for(int k=1; k<sum.at(i).size(); k++) sum.at(i).at(k) += sum.at(i).at(k-1);
        }
    };
    MergeSortTree(vector<vector<MS>> &A){ //各要素値1つに限らない Aの要素は全て昇順ソートされる.
        int N = A.size();
        while(siz < N) siz *= 2;
        dat.resize(siz<<1); sum.resize(siz<<1);
        for(int i=0; i<N; i++){
            sort(A.at(i).begin(),A.at(i).end()); //ここでソート.
            dat.at(i+siz) = A.at(i);
        }
        for(int i=siz-1; i>0; i--) merge(i,i*2,i*2+1);
        for(int i=1; i<2*siz; i++){
            sum.at(i) = dat.at(i);
            for(int k=1; k<sum.at(i).size(); k++) sum.at(i).at(k) += sum.at(i).at(k-1);
        }
    }
 
    int CountMoreEqual(int l,int r,MS x){ //範囲内のx以上の個数.
        int ret = 0;
        for(auto pos : findSegment(l,r)){
            ret += dat.at(pos).size()-(lower_bound(dat.at(pos).begin(),dat.at(pos).end(),x)-dat.at(pos).begin());
        }
        return ret;
    }
    int CountMore(int l,int r,MS x){return CountMoreEqual(l,r,x+1);} //x超過ver 小数有理数なら修正.
    long long SumMoreEqual(int l,int r,MS x){ //範囲内のx以上の総和.
        MS ret = 0;
        for(auto pos : findSegment(l,r)){
            int p = lower_bound(dat.at(pos).begin(),dat.at(pos).end(),x)-dat.at(pos).begin();
            ret += sum.at(pos).back();
            if(p > 0) ret -= sum.at(pos).at(p-1);
        }
        return ret;
    }
    long long SumMore(int l,int r,MS x){return SumMoreEqual(l,r,x+1);} //x超過ver
    int CountLess(int l,int r,MS x){ //範囲内のx未満の個数.
        int ret = 0;
        for(auto pos : findSegment(l,r)){
            ret += lower_bound(dat.at(pos).begin(),dat.at(pos).end(),x)-dat.at(pos).begin();
        }
        return ret;
    }
    int CountLessEqual(int l,int r,MS x){return CountLess(l,r,x+1);} //x以下ver
    long long SumLess(int l,int r,MS x){ //範囲内のx未満の総和.
        MS ret = 0;
        for(auto pos : findSegment(l,r)){
            int p = lower_bound(dat.at(pos).begin(),dat.at(pos).end(),x)-dat.at(pos).begin();
            if(p > 0) ret += sum.at(pos).at(p-1);
        }
        return ret;
    }
    long long SumLessEqual(int l,int r,MS x){return SumLess(l,r,x+1);} //x以下ver

    long long special(int l,int r,long long X){ //ゆきこ No.3078用
        long long ret = 0;
        for(auto pos : findSegment(l,r)){
            int p = lower_bound(dat.at(pos).begin(),dat.at(pos).end(),X)-dat.at(pos).begin();
            if(p > 0) ret += X*p-sum.at(pos).at(p-1);
            ret += (sum.at(pos).back()-(p>0?sum.at(pos).at(p-1):0))-X*(dat.at(pos).size()-p);
        }
        return ret;
    }  
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,Q; cin >> N >> Q;
    vector<long long> A(N);
    for(auto &a : A) cin >> a;
    MergeSortTree Z(A);

    while(Q--){
        long long l,r,X; cin >> l >> r >> X; l--;
        cout << Z.special(l,r,X) << "\n";
    }
}
0