結果
問題 | No.3078 Difference Sum Query |
ユーザー |
![]() |
提出日時 | 2025-03-28 21:22:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,641 ms / 2,000 ms |
コード長 | 6,346 bytes |
コンパイル時間 | 2,881 ms |
コンパイル使用メモリ | 216,520 KB |
実行使用メモリ | 166,612 KB |
最終ジャッジ日時 | 2025-03-28 21:23:32 |
合計ジャッジ時間 | 31,805 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define vi vector<int> #define vl vector<ll> #define vii vector<pair<int,int>> #define vll vector<pair<ll,ll>> #define vvi vector<vector<int>> #define vvl vector<vector<ll>> #define vvii vector<vector<pair<int,int>>> #define vvll vector<vector<pair<ll,ll>>> #define vst vector<string> #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define all(x) (x).begin(),(x).end() #define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end()) #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=300005,INF=15<<26; //2d point update rectangle sum // https://kopricky.github.io/code/SegmentTrees/rangetree_pointupdate.html template<typename T> class segtree { private: int n, sz; vector<T> node; public: void init(const vector<T>& v){ sz = (int)v.size(); n = 1; while(n < sz){ n *= 2; } node.assign(2*n, 0); for(int i = 0; i < sz; i++){ node[i+n] = v[i]; } for(int i=n-1; i>=1; i--){ node[i] = node[2*i] + node[2*i+1]; } } void update(int k, const T a) { node[k+=n] += a; while(k>>=1){ node[k] = node[2*k] + node[2*k+1]; } } T query(int a, int b) { T res1 = 0, res2 = 0; a += n, b += n; while(a != b){ if(a % 2) res1 = res1 + node[a++]; if(b % 2) res2 = res2 + node[--b]; a >>= 1, b >>= 1; } return res1 + res2; } void print(){ for(int i = 0; i < sz; i++){ cout << query(i, i+1) << " "; } cout << endl; } }; //座標の型, 値の型 template<typename CandidateType, typename ValueType> class RangeTree { public: static_assert(std::is_integral<CandidateType>::value, "Integral required."); private: using CT = CandidateType; using VT = ValueType; using pcc = pair<CT, CT>; using pci = pair<CT, int>; int n, sz; vector<segtree<VT> > seg; // y座標, x座標 vector<vector<pcc> > yx; // y座標, x座標 vector<pcc> sorted; void update_(int id, const CT x, const CT y, const VT val) { id += n-1; const int yid = lower_bound(all(yx[id]), pcc(y, x)) - yx[id].begin(); seg[id].update(yid, val); while(id > 0){ id = (id - 1) / 2; const int yid = lower_bound(all(yx[id]), pcc(y, x)) - yx[id].begin(); seg[id].update(yid, val); } } VT query(const int lxid, const int rxid, const CT ly, const CT ry, const int k, const int l, const int r) { if(r <= lxid || rxid <= l) return 0; if(lxid <= l && r <= rxid){ const int lyid = lower_bound(all(yx[k]), pcc(ly, numeric_limits<CT>::min())) - yx[k].begin(); const int ryid = upper_bound(all(yx[k]), pcc(ry, numeric_limits<CT>::min())) - yx[k].begin(); return (lyid >= ryid) ? 0 : seg[k].query(lyid, ryid); }else{ return query(lxid, rxid, ly, ry, 2*k+1, l, (l+r)/2) + query(lxid, rxid, ly, ry, 2*k+2, (l+r)/2, r); } } public: // 座標, 点の値 RangeTree(const vector<pcc>& cand, const vector<VT>& val) : n(1), sz((int)cand.size()), sorted(sz){ while(n < sz) n *= 2; for(int i = 0; i < sz; ++i){ sorted[i] = {cand[i].first, i}; } sort(all(sorted), [&](const pcc& a, const pcc& b){ return (a.first == b.first) ? (cand[a.second].second < cand[b.second].second) : (a.first < b.first); }); yx.resize(2*n-1), seg.resize(2*n-1); for(int i = 0; i < sz; ++i){ yx[i+n-1] = {{sorted[i].second, sorted[i].first}}; vector<VT> arg = {val[sorted[i].second]}; seg[i+n-1].init(arg); sorted[i].second = cand[sorted[i].second].second; } for(int i = n-2; i >= 0; --i){ yx[i].resize((int)yx[2*i+1].size() + (int)yx[2*i+2].size()); if(yx[i].empty()) continue; merge(all(yx[2*i+1]), all(yx[2*i+2]), yx[i].begin(), [&](const pcc& a, const pcc& b){ return (cand[a.first].second == cand[b.first].second) ? (a.second < b.second) : (cand[a.first].second < cand[b.first].second); }); vector<VT> arg((int)yx[i].size()); for(int j = 0; j < (int)yx[i].size(); ++j){ arg[j] = val[yx[i][j].first]; } seg[i].init(arg); } for(int i = 0; i < 2*n-1; ++i){ for(pcc& e : yx[i]){ e.first = cand[e.first].second; } } } // 点 (x,y) の更新を行う void update(const CT x, const CT y, const VT val){ const int id = lower_bound(all(sorted), pcc(x, y)) - sorted.begin(); return update_(id, x, y, val); } // [lx,rx) × [ly,ry) の長方形領域のクエリに答える VT query(const CT lx, const CT ly, const CT rx, const CT ry){ const int lxid = lower_bound(all(sorted), pcc(lx, numeric_limits<CT>::min())) - sorted.begin(); const int rxid = upper_bound(all(sorted), pcc(rx, numeric_limits<CT>::min())) - sorted.begin(); return (lxid >= rxid) ? 0 : query(lxid, rxid, ly, ry, 0, 0, n); } }; int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); ll N,Q;cin>>N>>Q; vll S(N); vl A(N),B(N); for(int i=0;i<N;i++){ ll x;cin>>x; S[i]=mp(i,x); A[i]=1; B[i]=x; } RangeTree<ll,ll> CN(S,A),SUM(S,B); vl rui(N+1); for(int i=0;i<N;i++){ rui[i+1]=rui[i]+B[i]; } ll M=10000000003LL; while(Q--){ ll l,r,x;cin>>l>>r>>x;l--; ll ans=0; ll a=CN.query(l,0,r,x); ll b=SUM.query(l,0,r,x); ans+=a*x; ans-=b; a=r-l-a; b=rui[r]-rui[l]-b; ans-=a*x; ans+=b; cout<<ans<<"\n"; } }