結果
問題 |
No.3078 Difference Sum Query
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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"; } }