結果
問題 | No.2065 Sum of Min |
ユーザー |
![]() |
提出日時 | 2022-09-02 21:36:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 307 ms / 2,000 ms |
コード長 | 2,044 bytes |
コンパイル時間 | 1,958 ms |
コンパイル使用メモリ | 187,320 KB |
実行使用メモリ | 10,648 KB |
最終ジャッジ日時 | 2024-11-16 02:37:19 |
合計ジャッジ時間 | 9,057 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename T> struct invertible_binary_indexed_tree{ int N; vector<T> BIT; function<T(T, T)> f; function<T(T)> inv; T E; invertible_binary_indexed_tree(){ } invertible_binary_indexed_tree(int N, function<T(T, T)> f, function<T(T)> inv, T E): N(N), BIT(N + 1, E), f(f), inv(inv), E(E){ } invertible_binary_indexed_tree(const vector<T> &A, function<T(T, T)> f, function<T(T)> inv, T E): N(A.size()), BIT(N + 1), f(f), inv(inv), E(E){ for (int i = 0; i < N; i++){ BIT[i + 1] = A[i]; } for (int i = 1; i < N; i++){ if (i + (i & -i) <= N){ BIT[i + (i & -i)] = f(BIT[i + (i & -i)], BIT[i]); } } } void add(int i, T x){ i++; while (i <= N){ BIT[i] = f(BIT[i], x); i += i & -i; } } T sum(int i){ T ans = E; while (i > 0){ ans = f(ans, BIT[i]); i -= i & -i; } return ans; } T sum(int l, int r){ return f(sum(r), inv(sum(l))); } }; int main(){ int N, Q; cin >> N >> Q; vector<long long> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; } vector<int> L(Q), R(Q), X(Q); for (int i = 0; i < Q; i++){ cin >> L[i] >> R[i] >> X[i]; L[i]--; } invertible_binary_indexed_tree<long long> BIT1(A, plus<long long>(), negate<long long>(), 0); invertible_binary_indexed_tree<int> BIT2(N, plus<int>(), negate<int>(), 0); vector<tuple<int, int, int>> query; for (int i = 0; i < N; i++){ query.push_back(make_tuple(A[i], 0, i)); } for (int i = 0; i < Q; i++){ query.push_back(make_tuple(X[i], 1, i)); } sort(query.begin(), query.end(), greater<tuple<int, int, int>>()); vector<long long> ans(Q); for (int i = 0; i < N + Q; i++){ int t = get<1>(query[i]); int p = get<2>(query[i]); if (t == 0){ BIT1.add(p, -A[p]); BIT2.add(p, 1); } if (t == 1){ ans[p] = BIT1.sum(L[p], R[p]) + (long long) X[p] * BIT2.sum(L[p], R[p]); } } for (int i = 0; i < Q; i++){ cout << ans[i] << endl; } }