#1175493 (C++17) No.3614 Breaking door keys（LITTLE BREAK ver.）

• 問題: No.3614 Breaking door keys（LITTLE BREAK ver.）
• ユーザー: GOTKAKO
• 提出日時: 2026-08-06 18:04:04
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 527 ms / 2,000 ms
• コード長: 2,955 bytes
• コンパイル時間: 1,544 ms
• コンパイル使用メモリ: 232,496 KB
• 実行使用メモリ: 92,288 KB
• 最終ジャッジ日時: 2026-08-06 18:04:18
• 合計ジャッジ時間: 13,646 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

サブタスク	配点	結果
サンプル	0 %	AC * 3
小課題1	10 %	AC * 7
小課題2	20 %	AC * 7
小課題3	30 %	AC * 7
小課題4	30 %	AC * 14
小課題5	10 %	AC * 38
合計	2.5 * 100% = 250 点

ソースコード

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

template <typename T>
class FenwickTree{
    private:
    vector<T> dat; 
    T sum(int r){
        T ret = 0;
        while(r > 0) ret += dat.at(r-1),r -= r&-r;
        return ret;
    }
    public:
    void make(int N){dat.resize(N);}
    void add(int pos,T v){
        pos++;
        while(pos <= dat.size()) dat.at(pos-1) += v,pos += pos&-pos;
    }
    void imos(int l,int r,T v){add(l,v),add(r,-v);} //[l,r) imos;
    T rangeans(int l,int r){return sum(r)-sum(l);}
    T get(int pos){return rangeans(pos,pos+1);} //imosはrange(0,pos+1);
};

struct MergeSortTree2{
    int siz,n;
    vector<vector<pair<int,long long>>> V;
    vector<FenwickTree<long long>> F,C;

    MergeSortTree2(vector<pair<long long,int>> All){
        n = All.size(),siz = 1;
        while(siz < n) siz += siz;
        V.resize(siz+siz),F.resize(siz+siz),C.resize(siz+siz);
        for(int i=0; i<n; i++) V.at(i+siz) = {{All.at(i).second,All.at(i).first}};
        for(int i=siz-1; i>0; i--){
            int pos1 = 0,pos2 = 0;
            int s1 = V.at(i*2).size(),s2 = V.at(i*2+1).size();
            auto &v = V.at(i),&V1 = V.at(i*2),&V2 = V.at(i*2+1);
            v.resize(s1+s2);
            int pos = 0;
            while(pos1 < s1 && pos2 < s2){
                if(V1.at(pos1).first <= V2.at(pos2).first) v.at(pos++) = V1.at(pos1++);
                else v.at(pos++) = V2.at(pos2++);
            }
            while(pos1 < s1) v.at(pos++) = V1.at(pos1++);
            while(pos2 < s2) v.at(pos++) = V2.at(pos2++);
        }
        for(int i=0; i<siz+siz; i++) F.at(i).make(V.at(i).size()),C.at(i).make(V.at(i).size());
    }
    void update(int pos,int c){
        pos += siz;
        auto now = V.at(pos).at(0);
        while(pos > 0){
            int p = lower_bound(V.at(pos).begin(),V.at(pos).end(),now)-V.at(pos).begin();
            F.at(pos).add(p,c*now.second),C.at(pos).add(p,c),pos >>= 1;
        }
    }
    long long query(int l,int r,int k){
        int pos = 1;
        long long ret = 0;
        while(pos < siz){
            auto &v = V.at(pos*2);
            int posl = lower_bound(v.begin(),v.end(),pair{l,-1LL})-v.begin();
            int posr = lower_bound(v.begin(),v.end(),pair{r,-1LL})-v.begin();
            long long c = C.at(pos*2).rangeans(posl,posr);
            if(c >= k){pos = pos*2; continue;}
            ret += F.at(pos*2).rangeans(posl,posr);
            k -= c,pos = pos*2+1;
        }
        ret += V.at(pos).at(0).second*k;
        return ret;
    }
};


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

    int N,Q; cin >> N >> Q;
    vector<pair<long long,int>> A(N);
    for(int i=0; i<N; i++){
        int s; cin >> s;
        A.at(i) = {s,i};
    }
    sort(A.begin(),A.end());

    MergeSortTree2 Z(A);
    for(int i=0; i<N; i++) Z.update(i,1);
    while(Q--){
        int l,r,k; cin >> l >> r >> k,l--;
        cout << Z.query(l,r,k) << "\n";
    }
}