結果
問題 | No.3078 Difference Sum Query |
ユーザー |
![]() |
提出日時 | 2025-03-28 22:12:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 310 ms / 2,000 ms |
コード長 | 7,193 bytes |
コンパイル時間 | 4,460 ms |
コンパイル使用メモリ | 315,032 KB |
実行使用メモリ | 61,936 KB |
最終ジャッジ日時 | 2025-03-28 22:12:30 |
合計ジャッジ時間 | 10,673 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; #pragma GCC target("popcnt") template <class D, auto D_build, class Q, auto Q_op, auto Q_e, auto D_query> struct AbstractWaveletMatrix { int height = 0; int n = 0; using storage_type = unsigned int; static constexpr int B = numeric_limits<storage_type>::digits, LowBits = __lg(B); static_assert(B == 1 << LowBits); struct BVecElem { storage_type v; int acc; }; struct BitVector; vector<BVecElem> bvecs_storage; vector<BitVector> bvecs; vector<D> D_data; struct BitVector { span<BVecElem> d; int zeros; BitVector(span<BVecElem> d, int k, const auto& a, auto& na) : d(d) { int n = size(a); int ptr0 = 0, ptr1 = n; for (int i = 0; i < n; i += B) { int len = min(B, n - i); storage_type x = 0; for (int i_low = 0; i_low < len; i_low++) { bool bit = a[i | i_low] >> k & 1; if (!bit) { na[ptr0++] = a[i | i_low]; } else { x |= storage_type(bit) << i_low; na[--ptr1] = a[i | i_low]; } } d[i >> LowBits].v = x; } assert(ptr0 == ptr1); zeros = ptr0; reverse(na.begin() + ptr0, na.begin() + n); for (int i = 0, sz = size(d); i + 1 < sz; i++) { d[i + 1].acc = d[i].acc + popcount(d[i].v); } } int rank1(int i) { auto di = d[i >> LowBits]; int low = i & (B - 1); auto mask = (storage_type(1) << low) - 1; return di.acc + popcount(di.v & mask); } int rank(bool b, int i) { return b == 0 ? i - rank1(i) : rank1(i); } int mv(bool b, int i) { return b == 0 ? i - rank1(i) : zeros + rank1(i); } }; AbstractWaveletMatrix() = default; template <class T> AbstractWaveletMatrix(vector<T> a) { auto mx = empty(a) ? 0 : *max_element(begin(a), end(a)); height = mx == 0 ? 0 : __lg(mx) + 1; n = size(a); int block_count = (n >> LowBits) + 1; bvecs_storage.resize(height * block_count); bvecs.reserve(height); vector<T> na(n); D_data.reserve(height + 1); D_data.emplace_back(D_build(a)); for (int k = height - 1; k >= 0; k--) { bvecs.emplace_back(span(begin(bvecs_storage) + k * block_count, block_count), k, a, na); swap(a, na); D_data.emplace_back(D_build(a)); } reverse(begin(bvecs), end(bvecs)); reverse(begin(D_data), end(D_data)); }; // returns the number of occurrence of x in a[l, r) int rank(auto x, int l, int r) { assert(0 <= l && l <= r && r <= n); if (x >> height) return 0; for (int k = height - 1; k >= 0; k--) { bool bit = x >> k & 1; l = bvecs[k].mv(bit, l); r = bvecs[k].mv(bit, r); } return r - l; } int rangefreq_below(auto vr, int l, int r) { assert(0 <= l && l <= r && r <= n); if (vr <= 0) return 0; if (vr >> height) return r - l; int res = 0; for (int k = height - 1; k >= 0; k--) { bool bit = vr >> k & 1; if (bit) { int ones_r = bvecs[k].rank1(r), ones_l = bvecs[k].rank1(l); res += (r - l) - (ones_r - ones_l); l = bvecs[k].zeros + ones_l; r = bvecs[k].zeros + ones_r; } else { l = bvecs[k].mv(bit, l); r = bvecs[k].mv(bit, r); } } return res; } // returns the number of occurrence of values in [vl, vr) in a[l, r) int rangefreq(auto vl, auto vr, int l, int r) { assert(vl <= vr); return rangefreq_below(vr, l, r) - rangefreq_below(vl, l, r); } Q rangequery_below(auto vr, int l, int r) { assert(0 <= l && l <= r && r <= n); if (vr <= 0) return Q_e(); if (vr >> height) return D_query(D_data[height], l, r); Q res = Q_e(); for (int k = height - 1; k >= 0; k--) { bool bit = vr >> k & 1; if (bit) { int ones_r = bvecs[k].rank1(r), ones_l = bvecs[k].rank1(l); res = Q_op(res, D_query(D_data[k], l - ones_l, r - ones_r)); l = bvecs[k].zeros + ones_l; r = bvecs[k].zeros + ones_r; } else { l = bvecs[k].mv(bit, l); r = bvecs[k].mv(bit, r); } } return res; } // returns the maximum vr s.t. # of points in [l, r) * [vl, vr) <= cnt_ub template <class T> T max_upper(T vl, int l, int r, int cnt_ub, T res_for_inf) { assert(0 <= l && l <= r && r <= n); assert(cnt_ub >= 0); assert(numeric_limits<T>::digits > height); cnt_ub += rangefreq_below(vl, l, r); if (cnt_ub >= r - l) return res_for_inf; T res = 0; for (int k = height - 1; k >= 0; k--) { int ones_l = bvecs[k].rank1(l), ones_r = bvecs[k].rank1(r); int zeros = (r - l) - (ones_r - ones_l); if (zeros <= cnt_ub) { cnt_ub -= zeros; res += T(1) << k; l = bvecs[k].zeros + ones_l; r = bvecs[k].zeros + ones_r; } else { l = l - ones_l; r = r - ones_r; } } return res; } template <class T> T min_lower(T vr, int l, int r, int cnt_ub) { assert(0 <= l && l <= r && r <= n); assert(cnt_ub >= 0); assert(numeric_limits<T>::digits > height); cnt_ub += (r - l) - rangefreq_below(vr, l, r); if (cnt_ub >= r - l) return 0; T res = T(1) << height; for (int k = height - 1; k >= 0; k--) { int ones_l = bvecs[k].rank1(l), ones_r = bvecs[k].rank1(r); int ones = ones_r - ones_l; if (ones <= cnt_ub) { cnt_ub -= ones; res -= T(1) << k; l = l - ones_l; r = r - ones_r; } else { l = bvecs[k].zeros + ones_l; r = bvecs[k].zeros + ones_r; } } return res; } }; struct S { int cnt; ll sm; }; vector<S> S_build(VL a) { int n = a.size(); vector<S> v(n + 1); rep(i, n) { v[i+1] = v[i]; v[i+1].cnt++; v[i+1].sm += a[i]; } return v; } S S_op(S x, S y) { return {x.cnt + y.cnt, x.sm + y.sm}; }; S S_e() { return {}; } S S_query(const vector<S>& v, int l, int r) { return {v[r].cnt - v[l].cnt, v[r].sm - v[l].sm}; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; VL a(n); rep(i, n) cin >> a[i]; AbstractWaveletMatrix<vector<S>, S_build, S, S_op, S_e, S_query> awm(a); rep(_, q) { int l, r; ll x; cin >> l >> r >> x; l--; auto [cl, sl] = awm.rangequery_below(x, l, r); auto [ctot, stot] = awm.rangequery_below((ll)1e12, l, r); int cu = ctot - cl; ll su = stot - sl; ll ans = su - 1LL * x * cu + 1LL * x * cl - sl; cout << ans << '\n'; } }