結果
問題 |
No.2065 Sum of Min
|
ユーザー |
|
提出日時 | 2025-07-01 10:02:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 400 ms / 2,000 ms |
コード長 | 7,240 bytes |
コンパイル時間 | 4,057 ms |
コンパイル使用メモリ | 302,244 KB |
実行使用メモリ | 24,176 KB |
最終ジャッジ日時 | 2025-07-01 10:02:25 |
合計ジャッジ時間 | 13,764 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct SuccinctIndexableDictionary { unsigned len, blk; vector<unsigned> bit, sum; SuccinctIndexableDictionary() = default; SuccinctIndexableDictionary(unsigned len): len(len), blk((len + 31) >> 5) { bit.assign(blk, 0U); sum.assign(blk, 0U); } void set(int k) { bit[k >> 5] |= 1U << (k & 31); } void build() { sum[0] = 0U; for(unsigned i = 1; i < blk; i++) { sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]); } } bool operator[](ll k) { return (bool((bit[k >> 5] >> (k & 31)) & 1)); } int rank(int k) { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); } int rank(bool val, int k) { return (val ? rank(k) : k - rank(k)); } }; template<typename T, ll MAXLOG> struct WaveletMatrix { ll len; SuccinctIndexableDictionary mat[MAXLOG]; ll mid[MAXLOG]; WaveletMatrix() = default; WaveletMatrix(vector<T> v): len(v.size()) { vector<T> l(len), r(len); for(ll lev = MAXLOG - 1; lev >= 0; lev--) { mat[lev] = SuccinctIndexableDictionary(len + 1); ll left = 0, right = 0; for(ll i = 0; i < len; i++) { if(((v[i] >> lev) & 1)) { mat[lev].set(i); r[right++] = v[i]; } else { l[left++] = v[i]; } } mid[lev] = left; mat[lev].build(); v.swap(l); for(ll i = 0; i < right; i++) { v[left + i] = r[i]; } } } pair<ll, ll> succ(bool f, ll l, ll r, ll lev) { return {mat[lev].rank(f, l) + mid[lev] * f, mat[lev].rank(f, r) + mid[lev] * f}; } T access(ll k) { T ret = 0; for(ll lev = MAXLOG - 1; lev >= 0; lev--) { bool f = mat[lev][k]; if(f) { ret |= T(1) << lev; } k = mat[lev].rank(f, k) + mid[lev] * f; } return ret; } T operator[](const ll &k) { return access(k); } ll rank(const T &x, ll r) { ll l = 0; for(ll lev = MAXLOG - 1; lev >= 0; lev--) { tie(l, r) = succ((x >> lev) & 1, l, r, lev); } return r - l; } T kth_smallest(ll l, ll r, ll k) { assert(0 <= k && k < r - l); T ret = 0; for(ll lev = MAXLOG - 1; lev >= 0; lev--) { ll cnt = mat[lev].rank(false, r) - mat[lev].rank(false, l); bool f = cnt <= k; if(f) { ret |= T(1) << lev; k -= cnt; } tie(l, r) = succ(f, l, r, lev); } return ret; } T kth_largest(ll l, ll r, ll k) { return kth_smallest(l, r, r - l - k - 1); } ll range_freq(ll l, ll r, T upper) { ll ret = 0; for(ll lev = MAXLOG - 1; lev >= 0; lev--) { bool f = ((upper >> lev) & 1); if(f) { ret += mat[lev].rank(false, r) - mat[lev].rank(false, l); } tie(l, r) = succ(f, l, r, lev); } return ret; } ll range_freq(ll l, ll r, T lower, T upper) { return range_freq(l, r, upper) - range_freq(l, r, lower); } T prev_value(ll l, ll r, T upper) { ll cnt = range_freq(l, r, upper); return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1); } T next_value(ll l, ll r, T lower) { ll cnt = range_freq(l, r, lower); return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt); } }; template<typename T = ll, ll MAXLOG = 20> struct CompressedWaveletMatrix { WaveletMatrix<ll, MAXLOG> mat; vector<T> ys; CompressedWaveletMatrix() {} CompressedWaveletMatrix(const vector<T> &v): ys(v) { ranges::sort(ys); ys.erase(unique(ys.begin(), ys.end()), ys.end()); vector<ll> t(v.size()); for(ll i = 0; i < (ll)v.size(); i++) { t[i] = get(v[i]); } mat = WaveletMatrix<ll, MAXLOG>(t); } inline ll get(const T &x) { return ranges::lower_bound(ys, x) - ys.begin(); } T access(ll k) { return ys[mat.access(k)]; } T operator[](const ll &k) { return access(k); } ll rank(const T &x, ll r) { auto pos = get(x); if(pos == (ll)ys.size() || ys[pos] != x) { return 0; } return mat.rank(pos, r); } ll count(ll l, ll r, T x) { if(l >= r) { return 0; } return rank(x, r) - rank(x, l); } T kth_smallest(ll l, ll r, ll k) { return ys[mat.kth_smallest(l, r, k)]; } T kth_largest(ll l, ll r, ll k) { return ys[mat.kth_largest(l, r, k)]; } ll range_freq(ll l, ll r, T upper) { if(l >= r) { return 0; } return mat.range_freq(l, r, get(upper)); } ll range_freq(ll l, ll r, T lower, T upper) { if(l >= r || lower >= upper) { return 0; } return mat.range_freq(l, r, get(lower), get(upper)); } T prev_value(ll l, ll r, T upper) { auto ret = mat.prev_value(l, r, get(upper)); return ret == -1 ? T(-1) : ys[ret]; } T next_value(ll l, ll r, T lower) { auto ret = mat.next_value(l, r, get(lower)); return ret == -1 ? T(-1) : ys[ret]; } }; template<typename T, int MAXLOG> struct WaveletMatrixRectangleSum { int len; SuccinctIndexableDictionary mat[MAXLOG]; vector<T> ws[MAXLOG]; int mid[MAXLOG]; WaveletMatrixRectangleSum() = default; WaveletMatrixRectangleSum(const vector<T> &v, const vector<T> &w): len(v.size()) { assert(v.size() == w.size()); vector<int> l(len), r(len), ord(len); iota(ord.begin(), ord.end(), 0); for(int lev = MAXLOG - 1; lev >= 0; lev--) { mat[lev] = SuccinctIndexableDictionary(len + 1); int left = 0, right = 0; for(int i = 0; i < len; i++) { if((v[ord[i]] >> lev) & 1) { mat[lev].set(i); r[right++] = ord[i]; } else { l[left++] = ord[i]; } } mid[lev] = left; mat[lev].build(); ord.swap(l); for(int i = 0; i < right; i++) { ord[left + i] = r[i]; } ws[lev].resize(len + 1); ws[lev][0] = 0; for(int i = 0; i < len; i++) { ws[lev][i + 1] = ws[lev][i] + w[ord[i]]; } } } pair<int, int> succ(bool f, int l, int r, int lev) { return {mat[lev].rank(f, l) + mid[lev] * f, mat[lev].rank(f, r) + mid[lev] * f}; } T sum(int l, int r, T upper) { T ret = 0; for(int lev = MAXLOG - 1; lev >= 0; lev--) { bool f = (upper >> lev) & 1; if(f) { ret += ws[lev][mat[lev].rank(false, r)] - ws[lev][mat[lev].rank(false, l)]; } tie(l, r) = succ(f, l, r, lev); } return ret; } T sum(int l, int r, T lower, T upper) { return sum(l, r, upper) - sum(l, r, lower); } }; template<typename T = ll, int MAXLOG = 20> struct CompressedWaveletMatrixRectangleSum { WaveletMatrixRectangleSum<T, MAXLOG> mat; vector<T> ys; CompressedWaveletMatrixRectangleSum(const vector<T> &v, const vector<T> &w): ys(v) { ranges::sort(ys); ys.erase(unique(ys.begin(), ys.end()), ys.end()); vector<T> t(v.size()); for(int i = 0; i < (int)v.size(); i++) { t[i] = get(v[i]); } mat = WaveletMatrixRectangleSum<ll, MAXLOG>(t, w); } inline int get(const T &x) { return ranges::lower_bound(ys, x) - ys.begin(); } T sum(int l, int r, T upper) { return mat.sum(l, r, get(upper)); } T sum(int l, int r, T lower, T upper) { return mat.sum(l, r, get(lower), get(upper)); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N, Q; cin >> N >> Q; vector<ll> A(N); for(auto &i : A) { cin >> i; } CompressedWaveletMatrix<> W(A); CompressedWaveletMatrixRectangleSum<> S(A, A); while(Q--) { ll L, R, X; cin >> L >> R >> X; L--; cout << S.sum(L, R, X) + X * W.range_freq(L, R, X, 2e9) << "\n"; } }