結果
問題 | 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;}}