結果
問題 |
No.3078 Difference Sum Query
|
ユーザー |
|
提出日時 | 2025-03-28 21:54:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 928 ms / 2,000 ms |
コード長 | 3,211 bytes |
コンパイル時間 | 3,602 ms |
コンパイル使用メモリ | 295,908 KB |
実行使用メモリ | 89,344 KB |
最終ジャッジ日時 | 2025-03-28 21:55:07 |
合計ジャッジ時間 | 19,457 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); ++i) using namespace std; using ll = long long; struct Node { Node *left, *right; int cnt; ll sum; Node() : left(nullptr), right(nullptr), cnt(0), sum(0) {} }; vector<Node*> roots; int main() { int n, q; cin >> n >> q; vector<ll> a(n); rep(i, n) cin >> a[i]; vector<ll> sorted_unique = a; sort(sorted_unique.begin(), sorted_unique.end()); sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()), sorted_unique.end()); int m = sorted_unique.size(); vector<ll> prefix_sum(n+1); rep(i, n) { prefix_sum[i + 1] = prefix_sum[i] + a[i]; } roots.resize(n+1); roots[0] = new Node(); for (int i = 1; i <= n; ++i) { ll val = a[i-1]; int pos = lower_bound(sorted_unique.begin(), sorted_unique.end(), val) - sorted_unique.begin(); Node* prev_root = roots[i - 1]; Node* new_root = new Node(); roots[i] = new_root; stack<tuple<Node*, Node*, int, int>> st; st.emplace(prev_root, new_root, 0, m - 1); while (!st.empty()) { auto [prev, curr, l, r] = st.top(); st.pop(); int prev_cnt = 0; ll prev_sum = 0; if (prev) { prev_cnt = prev->cnt; prev_sum = prev->sum; } curr->cnt = prev_cnt + 1; curr->sum = prev_sum + val; if (l == r) continue; int mid = (l + r) / 2; if (pos <= mid) { curr->right = (prev ? prev->right : nullptr); curr->left = new Node(); st.emplace((prev ? prev->left : nullptr), curr->left, l, mid); } else { curr->left = (prev ? prev->left : nullptr); curr->right = new Node(); st.emplace((prev ? prev->right : nullptr), curr->right, mid + 1, r); } } } // 查询函数 function<pair<int, ll>(Node*, int, int, int)> query = [&](Node* node, int l, int r, int k) -> pair<int, ll> { if (!node || l > k) return {0, 0}; if (r <= k) return {node->cnt, node->sum}; int mid = (l + r) / 2; auto left_res = query(node->left, l, mid, k); if (k > mid) { auto right_res = query(node->right, mid + 1, r, k); left_res.first += right_res.first; left_res.second += right_res.second; } return left_res; }; rep(qi, q) { int L, R; ll X; cin >> L >> R >> X; L--; R--; ll sum_total = prefix_sum[R + 1] - prefix_sum[L]; int T = R - L + 1; int k = upper_bound(sorted_unique.begin(), sorted_unique.end(), X) - sorted_unique.begin() - 1; int K = 0; ll S_less = 0; if (k >= 0) { auto [cnt_R, sum_R] = query(roots[R + 1], 0, m - 1, k); auto [cnt_L, sum_L] = query(roots[L], 0, m - 1, k); K = cnt_R - cnt_L; S_less = sum_R - sum_L; } ll sum_abs = sum_total - 2 * S_less + X * (2 * K - T); cout << sum_abs << '\n'; } return 0; }