#1187002 (C++17) No.924 紲星

• 問題: No.924 紲星
• ユーザー: GOTKAKO
• 提出日時: 2026-09-16 05:20:30
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2,161 ms / 4,000 ms
• コード長: 3,438 bytes
• コンパイル時間: 2,013 ms
• コンパイル使用メモリ: 233,112 KB
• 実行使用メモリ: 187,520 KB
• 最終ジャッジ日時: 2026-09-16 05:21:33
• 合計ジャッジ時間: 23,335 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 16

ソースコード

#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 KotonohaAkane{
    int siz,n;
    vector<vector<pair<int,long long>>> V;
    vector<FenwickTree<long long>> F,C;

    KotonohaAkane(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 pos = 1,left = (r-l+1)/2;
        long long small = 0,big = 0,inf = 1e18;
        while(pos < siz){
            auto &vl = V.at(pos*2),&vr = V.at(pos*2+1);
            int posll = lower_bound(vl.begin(),vl.end(),pair{l,-inf})-vl.begin();
            int poslr = lower_bound(vl.begin(),vl.end(),pair{r,-inf})-vl.begin();
            int posrl = lower_bound(vr.begin(),vr.end(),pair{l,-inf})-vr.begin();
            int posrr = lower_bound(vr.begin(),vr.end(),pair{r,-inf})-vr.begin();
            int cl = C.at(pos*2).rangeans(posll,poslr);
            int cr = C.at(pos*2+1).rangeans(posrl,posrr);
            long long sl = F.at(pos*2).rangeans(posll,poslr);
            long long sr = F.at(pos*2+1).rangeans(posrl,posrr);

            if(left <= cl) big += sr,pos = pos*2;
            else small += sl,left -= cl,pos = pos*2+1;
        }
        long long x = V.at(pos).at(0).second;
        small += x;
        long long ret = x*((r-l+1)/2)-small;
        ret += big-x*(r-l-(r-l+1)/2);
        return ret;
    }
};


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

    int N,Q; cin >> N >> Q;
    vector<pair<long long,int>> All(N);
    for(int i=0; i<N; i++){
        int a; cin >> a;
        All.at(i) = {a,i};
    }
    sort(All.begin(),All.end());
    KotonohaAkane Z(All);
    for(int i=0; i<N; i++) Z.update(i,1);
    while(Q--){
        int l,r; cin >> l >> r,l--;
        cout << Z.query(l,r) << "\n";
    }
}