結果

問題 No.3078 Difference Sum Query
コンテスト
ユーザー umimel
提出日時 2025-03-28 22:07:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 499 ms / 2,000 ms
コード長 2,250 bytes
コンパイル時間 1,883 ms
コンパイル使用メモリ 173,732 KB
実行使用メモリ 63,592 KB
最終ジャッジ日時 2025-03-28 22:07:48
合計ジャッジ時間 12,068 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘std::pair<int, long long int> rangefreq::query(int, int, ll, int, int, int) const’:
main.cpp:50:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   50 |             auto [cnt1, sum1] = query(a, b, x, k*2+1, l, (l+r)/2);
      |                  ^
main.cpp:51:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   51 |             auto [cnt2, sum2] = query(a, b, x, k*2+2, (l+r)/2, r);
      |                  ^
main.cpp: In function ‘void solve()’:
main.cpp:70:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   70 |         auto [cnt, sum1] = freq.query(l, r+1, x);
      |              ^

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;


struct rangefreq{
	int n;
	vector<vector<ll>> dat;
    vector<vector<ll>> sum;

	rangefreq(const vector<ll> &v={}){
		n = 1;
		while(n < v.size()) n <<= 1;
		dat.assign(2*n-1, {});
        sum.assign(2*n-1, {0});
		for(int i=0;i<v.size();i++) dat[i+n-1].push_back(v[i]);
        for(int i=0;i<v.size();i++) sum[i+n-1].push_back(sum[i+n-1].back()+v[i]);
		for(int i=n-2;i>=0;i--){
			dat[i].resize(dat[i*2+1].size()+dat[i*2+2].size());
			merge(dat[i*2+1].begin(),dat[i*2+1].end(),
				dat[i*2+2].begin(),dat[i*2+2].end(),
				dat[i].begin()
			);
            for(int j=0;j<dat[i].size();j++){
                sum[i].push_back(sum[i].back()+dat[i][j]);
            }
		}
	}

	pair<int, ll> query(int a, int b, ll x, int k=0, int l=0, int r=-1) const //[a,b) count(*<x)
	{
		if(r<0)r=n;
		if(b<=l||r<=a) return {0, 0LL};
		else if(a<=l&&r<=b){
            int cnt = lower_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin();
            return {cnt, sum[k][cnt]};
        }else{
            auto [cnt1, sum1] = query(a, b, x, k*2+1, l, (l+r)/2);
            auto [cnt2, sum2] = query(a, b, x, k*2+2, (l+r)/2, r);
            return {cnt1 + cnt2, sum1 + sum2};
        }
	}
};

void solve(){
    int n, q; cin >> n >> q;
    vector<ll> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    vector<ll> sum(n+1, 0LL); for(int i=0; i<n; i++) sum[i+1] = sum[i] + a[i];
    rangefreq freq(a);

    while(q--){
        int l, r; cin >> l >> r;
        l--; r--;
        ll x; cin >> x;
        int len = r - l + 1;
        ll s = sum[r+1] - sum[l];
        auto [cnt, sum1] = freq.query(l, r+1, x);
        cout << (ll)cnt*x - sum1 + (s - sum1) - (ll)(len - cnt)*x << '\n';
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T=1;
    //cin >> T;
    while(T--) solve();
}
0