結果

問題 No.3078 Difference Sum Query
コンテスト
ユーザー srjywrdnprkt
提出日時 2025-03-28 23:07:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,673 bytes
コンパイル時間 3,952 ms
コンパイル使用メモリ 293,172 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-28 23:07:52
合計ジャッジ時間 8,549 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

const int sz=1e5+1;
ll res[sz], X[sz];
int l[sz], r[sz];

// Mo's Algorithm
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll N, M, Q, S=0;
    ll ans=0;
    cin >> N >> Q;
    vector<ll> A(N), B;
    for (int i=0; i<N; i++){
        cin >> A[i];
        S += A[i];
    }
    B = A;
    sort(B.begin(), B.end());

    M = sqrt(N);
    vector<int> idx(Q);
    iota(idx.begin(), idx.end(), 0);
    for (int i=0; i<Q; i++){
        cin >> l[i] >> r[i] >> X[i];
        l[i]--;
    }
 
    sort(idx.begin(), idx.end(), [&](int a, int b){
        if (l[a]/M != l[b]/M) return l[a] < l[b];
        if (l[a]/M & 1) return r[a] > r[b];
        return r[a] < r[b];
    });

    fenwick_tree<ll> tc(N+1), ts(N+1);

    auto add=[&](int x){
        int z = lower_bound(B.begin(), B.end(), A[x])-B.begin();
        ts.add(z, A[x]);
        tc.add(z, 1);
    };
 
    auto del=[&](int x){
        int z = lower_bound(B.begin(), B.end(), A[x])-B.begin();
        ts.add(z, -A[x]);
        tc.add(z, -1);
    };
 
    int nl=0, nr=0;
    for (auto &i : idx){
        while(nl > l[i]) add(--nl);
        while(nr < r[i]) add(nr++);
        while(nl < l[i]) del(nl++); 
        while(nr > r[i]) del(--nr);
        int z = lower_bound(B.begin(), B.end(), X[i])-B.begin();
        ll s = ts.sum(0, z), c = tc.sum(0, z), s2 = ts.sum(z, N+1), c2 = tc.sum(z, N+1);
        res[i] = c*X[i]-s+s2-c2*X[i];
    }
 
    for (int i=0; i<Q; i++) cout << res[i] << '\n';
 
    return 0;
}
0