結果

問題 No.3078 Difference Sum Query
ユーザー iomir
提出日時 2025-03-28 22:29:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,104 ms / 2,000 ms
コード長 4,021 bytes
コンパイル時間 4,099 ms
コンパイル使用メモリ 294,452 KB
実行使用メモリ 62,328 KB
最終ジャッジ日時 2025-03-28 22:30:19
合計ジャッジ時間 25,537 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

#define all(v) v.begin(),v.end()
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using vll=vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,ll>;
using vp=vector<pair<ll, ll>>;
//using mint=modint1000000007;
//using mint=modint998244353;

const ll INF=1ll<<60;
ll mod10=1e9+7;
ll mod99=998244353;
const double PI = acos(-1);

#define rep(i,n) for (ll i=0;i<n;++i)
#define per(i,n) for(ll i=n-1;i>=0;--i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
#define per2(i,a,n) for (ll i=a;i>=n;--i)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }


template<typename T>
struct merge_sort_tree{
    ll N=1;
    vector<vector<T>> node;
    vector<vector<T>> rw;
    merge_sort_tree(vector<T>& vec){
        while(N<(ll)vec.size()) N*=2;
        node.resize(2*N-1);
        rw.resize(2*N-1);
        for(int i=0;i<(int)vec.size();i++) node[N-1+i].push_back(vec[i]);
        for(int i=N-2;i>=0;i--){
            merge(node[2*i+1].begin(),node[2*i+1].end(),node[2*i+2].begin(),node[2*i+2].end(),back_inserter(node[i]));
        }
    
        for(int i=0;i<2*N-1;i++){
            rw[i].push_back(0);
            for(int j=0;j<(int)node[i].size();j++){
                rw[i].push_back(node[i][j]+rw[i][j]);
            }
        }
    }

    //[a,b)でx以下のものの個数
    ll cntlesseq(ll a,ll b,T x){return cntlesseq_sub(a,b,x,0,0,N);}
    ll cntlesseq_sub(ll a,ll b,T x,ll k,ll l,ll r){
        if(r<=a||b<=l) return 0;
        else if(a<=l&&r<=b){
            return upper_bound(all(node[k]),x)-node[k].begin();
        }else{
            return cntlesseq_sub(a,b,x,2*k+1,l,(l+r)/2)+cntlesseq_sub(a,b,x,2*k+2,(l+r)/2,r);
        }
    }
    //[a,b)でx未満のものの個数
    ll cntless(ll a,ll b,T x){return cntlesseq(a,b,x-1);}

    //[a,b)でx以上のものの個数
    ll cntmoreeq(ll a,ll b,T x){return b-a-cntlesseq(a,b,x-1);};
    //[a,b)でxより大きいものの個数
    ll cntmore(ll a,ll b,T x){return b-a-cntlesseq(a,b,x);};


    //[a,b)でx以下のものの総和
    T sumlesseq(ll a,ll b,T x){return sumlesseq_sub(a,b,x,0,0,N);}
    T sumlesseq_sub(ll a,ll b,T x,ll k,ll l,ll r){
        if(r<=a||b<=l) return 0;
        else if(a<=l&&r<=b){
            return rw[k][upper_bound(all(node[k]),x)-node[k].begin()];
        }else{
            return sumlesseq_sub(a,b,x,2*k+1,l,(l+r)/2)+sumlesseq_sub(a,b,x,2*k+2,(l+r)/2,r);
        }
    }
    //[a,b)でx未満のものの総和
    T sumless(ll a,ll b,T x){return sumlesseq(a,b,x-1);}

    //[a,b)でx以上のものの総和
    T summoreeq(ll a,ll b,T x){return summoreeq_sub(a,b,x,0,0,N);}
    T summoreeq_sub(ll a,ll b,T x,ll k,ll l,ll r){
        if(r<=a||b<=l) return 0;
        else if(a<=l&&r<=b){
            return rw[k][rw[k].size()-1]-rw[k][lower_bound(all(node[k]),x)-node[k].begin()];
        }else{
            return summoreeq_sub(a,b,x,2*k+1,l,(l+r)/2)+summoreeq_sub(a,b,x,2*k+2,(l+r)/2,r);
        }
    }
    //[a,b)でxより大きいものの総和
    T summore(ll a,ll b,T x){return summoreeq(a,b,x+1);};

    //[l,r)でｋ番目に小さい数
    long long Kthsmallest(ll a,ll b,ll x){
        if(x>b-a) return -1;
        ll l=-1,r=1e18;
        while(r-l>1){
            ll m=(r+l)/2;
            if(cntlesseq(a,b,m)>=x) r=m;
            else l=m;
        }
        return r;
    }
};


bool solve(){
    ll N,Q;cin>>N>>Q;
    vll A(N);rep(i,N) cin>>A[i];
    merge_sort_tree<ll> mst(A);
    
    rep(_,Q){
        ll l,r,x;cin>>l>>r>>x;
        l--;
        ll ans=0;
        ans+=-mst.sumless(l,r,x)+mst.summoreeq(l,r,x);
        ans+=mst.cntless(l,r,x)*x-mst.cntmoreeq(l,r,x)*x;
        cout<<ans<<endl;
    }
    return 0;
}




int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   ll T=1;//cin>>T;
   rep(i,T) solve();
}
0