結果

問題 No.3078 Difference Sum Query
ユーザー srjywrdnprkt
提出日時 2025-03-29 00:10:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 174 ms / 2,000 ms
コード長 1,371 bytes
コンパイル時間 3,573 ms
コンパイル使用メモリ 290,488 KB
実行使用メモリ 15,488 KB
最終ジャッジ日時 2025-03-29 00:10:42
合計ジャッジ時間 8,592 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/fenwicktree>

using namespace std;
using namespace atcoder;
using ll = long long;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       平面走査でやる。
       L_i-1のところで-
       R_iのところで+する。
       縦方向はfenwick treeで
    */

    ll N, Q, L, R;
    cin >> N >> Q;
    vector<ll> A(N), B;
    for (int i=0; i<N; i++) cin >> A[i];
    vector<vector<pair<ll, ll>>> v(N+1); //横方向ごとにクエリインデックス、+か-か 
    vector<ll> ans(Q), X(Q);
    for (int i=0; i<Q; i++){
        cin >> L >> R >> X[i];
        v[L-1].push_back({i, -1});
        v[R].push_back({i, 1});
    }
    B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    fenwick_tree<ll> tc(N+1), ts(N+1);
    for (int i=0; i<=N; i++){
        if (i){
            ll z = lower_bound(B.begin(), B.end(), A[i-1])-B.begin();
            tc.add(z, 1);
            ts.add(z, A[i-1]);
        }
        for (auto [idx, sign] : v[i]){
            ll x = X[idx], z = upper_bound(B.begin(), B.end(), x)-B.begin();
            ll c1 = tc.sum(0, z), c2 = tc.sum(z, N+1), s1 = ts.sum(0, z), s2 = ts.sum(z, N+1);
            ans[idx] += sign * (c1*x-s1+s2-c2*x);
        }
    }
    for (int i=0; i<Q; i++) cout << ans[i] << '\n';

    return 0;
}
0