結果

問題 No.3078 Difference Sum Query
ユーザー graph11463
提出日時 2025-04-03 14:03:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 746 ms / 2,000 ms
コード長 2,942 bytes
コンパイル時間 1,778 ms
コンパイル使用メモリ 110,888 KB
実行使用メモリ 57,048 KB
最終ジャッジ日時 2025-04-03 14:03:25
合計ジャッジ時間 16,191 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll =long long;
vector<ll> SumVec(vector<ll> base){
    vector<ll> res;
    res.resize(base.size()+1);
    for(int i=0;i<base.size();i++){
        res[i+1]=res[i]+base[i];
    }
    return res;
}
struct SegVec{
    vector<vector<ll>> node;
    vector<vector<ll>> nodeSum;
    ll n,sz,log;
    SegVec() : SegVec(0){}
    SegVec(ll N) : SegVec(vector<ll>(N,0)){}
    SegVec(vector<ll> vec) : n(vec.size()){
        sz=1;
        log=0;
        while(n>sz){
            sz*=2;
            log++;
        }
        node.resize(2*sz);
        nodeSum.resize(2*sz);
        for(ll i=0;i<n;i++){
            node[sz+i].push_back(vec[i]);
        }
        for(ll i=sz-1;i>0;i--){
            for(ll j=0;j<node[i*2].size();j++){
                node[i].push_back(node[i*2][j]);
            }
            for(ll j=0;j<node[i*2+1].size();j++){
                node[i].push_back(node[i*2+1][j]);
            }
            sort(node[i].begin(),node[i].end());
        }
        for(ll i=2*sz-1;i>0;i--){
            nodeSum[i]=SumVec(node[i]);
        }
    }
    void dbg(ll p,int k=1){
        cout << "dbg: "<< p << ": ";
        cout << "{ ";
        for(auto v:node[p]){
            cout << v <<",";
        }
        cout << "} ";
        if(k){
            cout << endl;
        }else{
            cout <<", ";
        }
        return;
    }
    void dbg_all(){
        for(ll i=0;i<=log;i++){
            for(ll j=(1LL<<i);j<(1LL<<(i+1));j++){
                dbg(j,0);
            }
            cout << endl;
        }
    }
    ll get(int l, int r,ll x){
        ll ans=0;
        l += sz;
        r += sz;
        while (l < r) {
            if (l & 1){
                auto It=lower_bound(node[l].begin(),node[l].end(),x);
                ans+=nodeSum[l].back()-nodeSum[l][It-node[l].begin()]-x*(nodeSum[l].size()-(It-node[l].begin())-1);
                //cout << "L: "<< It-node[l].begin()<< endl;
                //cout << ans << endl;
                //dbg(l);
                ans+=x*(It-node[l].begin())-nodeSum[l][It-node[l].begin()];
                l++;
            }
            if (r & 1){
                r--;
                auto It=lower_bound(node[r].begin(),node[r].end(),x);
                //cout << "R: "s<< It-node[r].begin()<< endl;
                //dbg(r);
                ans+=nodeSum[r].back()-nodeSum[r][It-node[r].begin()]-x*(nodeSum[r].size()-(It-node[r].begin())-1);
                ans+=x*(It-node[r].begin())-nodeSum[r][It-node[r].begin()];
            }
            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
    
};
void solve(){
    int N,Q;cin >> N >> Q;
    vector<ll> A(N);
    for(auto &v:A){
        cin >> v;
    }
    SegVec seg(A);
    for(int i=0;i<Q;i++){
        ll l,r,x;cin >> l >> r >>x;
        l--;
        cout << seg.get(l,r,x) << endl;
    }
}
int main(){
    solve();
    return 0;
}
0