結果
問題 |
No.3078 Difference Sum Query
|
ユーザー |
![]() |
提出日時 | 2025-03-28 22:07:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 372 ms / 2,000 ms |
コード長 | 5,715 bytes |
コンパイル時間 | 2,767 ms |
コンパイル使用メモリ | 219,468 KB |
実行使用メモリ | 14,796 KB |
最終ジャッジ日時 | 2025-03-28 22:08:15 |
合計ジャッジ時間 | 10,635 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
//#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; using pli = pair<ll,int>; #define TEST cerr << "TEST" << endl #define AMARI 998244353 //#define AMARI 1000000007 #define el '\n' #define El '\n' #define YESNO(x) ((x) ? "Memo" : "Numo") #define YES YESNO(true) #define NO YESNO(false) #define REV_PRIORITY_QUEUE(tp) priority_queue<tp,vector<tp>,greater<tp>> #define NO_ANS(x) {cout << (x) << '\n'; return;} template <typename T> void inline VEC_UNIQ(vector<T> &v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return; } //座標圧縮 template <typename T> vector<int> ococo_cordinate_compression(vector<T> a){ int n = a.size(); vector<T> temp = a; sort(temp.begin(),temp.end()); temp.erase(unique(temp.begin(),temp.end()),temp.end()); vector<int> ans(n); for(int i = 0; i < n; i++){ typename vector<T>::iterator it = lower_bound(temp.begin(),temp.end(),a[i]); int idx = distance(temp.begin(),it); ans[i] = idx; } return ans; } // 抽象再帰セグ木?(抽象セグ木の定義分からんな)(遅延ではない) // ococo_segtree<int> rsq(n,0);みたいに宣言する template <typename T> class ococo_segtree { T func(T a, T b) { // ここに演算を入れる return (a + b); } public: int n; T tmax; // range minimum query vector<T> rmq; //(データの大きさ,単位元) ococo_segtree(int N, T t) { syokica(N, t); } // 配列の初期化 O(N) void syokica(int a, T t) { n = 1; tmax = t; while(n < a) n *= 2; rmq.resize(2 * n - 1); for(int i = 0; i < 2 * n - 1; i++) { rmq[i] = tmax; } } // a[i]をxにする O(logN) void update_num(int i, T x) { i += (n - 1); rmq[i] = x; while(i) { i = (i - 1) / 2; rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]); } } // a[i]にxを加える O(logN) void add_num(int i, T x) { i += (n - 1); rmq[i] += x; while(i) { i = (i - 1) / 2; rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]); } } T get_minimum2(int a, int b, int k, int l, int r) { if(a <= l && r <= b) return rmq[k]; else if(r <= a || b <= l) return tmax; else return func(get_minimum2(a, b, k * 2 + 1, l, (l + r) / 2), get_minimum2(a, b, k * 2 + 2, (l + r) / 2, r)); } //[l,r)の区間演算の取得 O(logN) T get_val(int l, int r) { return get_minimum2(l, r, 0, 0, n); } }; #define MULTI_TEST_CASE false void solve(void){ //問題を見たらまず「この問題設定から言えること」をいっぱい言う //一個回答に繋がりそうな解法が見えても、実装や細かい詰めに時間がかかりそうなら別の方針を考えてみる //ある程度考察しても全然取っ掛かりが見えないときは実験をしてみる //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く //複数の解法のアイデアを思いついた時は全部メモしておく //g++ -D_GLIBCXX_DEBUG -Wall -Wextra -O2 e.cpp -o o //多分座標圧縮 + Mo 実装がヤバい! //↑実は Mo はいらなくて、[1,L-1] と [1,R] の和が分かれば良い int n,q; cin >> n >> q; vector<ll> a(n); for(int i = 0; i < n; i++){ cin >> a[i]; } vector<int> idxa = ococo_cordinate_compression<ll>(a); vector<ll> b = a; VEC_UNIQ(b); vector<ll> ans(q); //query[i] = idx,x,plusならtrue,query_idx vector<tuple<int,ll,bool,int>> query(2 * q); for(int i = 0; i < q; i++){ int l,r; cin >> l >> r; l--; r--; ll x; cin >> x; query[2 * i] = tuple(l - 1,x,false,i); query[2 * i + 1] = tuple(r,x,true,i); } sort(query.begin(),query.end()); int l = -1; ococo_segtree<ll> sum(n + 1,0LL),cnt(n + 1,0LL); for(int i = 0; i < 2 * q; i++){ int idx,query_idx; ll x; bool plus; tie(idx,x,plus,query_idx) = query[i]; if(idx == -1)continue; while(l != idx){ l++; //a[l] の情報をセグ木に乗せる vector<ll>::iterator it = lower_bound(b.begin(),b.end(),a[l]); int idxal = distance(b.begin(),it); sum.add_num(idxal,a[l]); cnt.add_num(idxal,1LL); } //x が座標圧縮後のどの値に対応する? vector<ll>::iterator it = lower_bound(b.begin(),b.end(),x); //x は idxx 以上で、idxx+1 より小さ`い int idxx = distance(b.begin(),it); ll temp_val = sum.get_val(idxx,n + 1) - cnt.get_val(idxx,n + 1) * x; temp_val -= (sum.get_val(0,idxx) - cnt.get_val(0,idxx) * x); if(plus)ans[query_idx] += temp_val; if(!plus)ans[query_idx] -= temp_val; //cerr << sum.get_val(idxx + 1,n + 1) << ' ' << cnt.get_val(idxx + 1,n + 1) << ' ' << sum.get_val(0,idxx + 1) << ' ' << cnt.get_val(0,idxx + 1) << el; //cerr << idx << ' ' << x << ' ' << temp_val << el; } for(int i = 0; i < q; i++){ cout << ans[i] << el; } return; } void calc(void){ return; } signed main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE)cin >> t; while(t--){ solve(); } return 0; }