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

• 問題: No.924 紲星
• ユーザー: kyawa
• 提出日時: 2021-12-17 18:23:00
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 6,042 bytes
• コンパイル時間: 3,053 ms
• コンパイル使用メモリ: 232,468 KB
• 最終ジャッジ日時: 2025-01-27 01:56:03
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 15 WA * 1

ソースコード

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

class WaveletMatrix{
public:
    long bitsize;
    vector<long> table_origin;
    vector<long> table_sorted;
    
    WaveletMatrix(vector<long> table) : table_origin(table){
        long table_max = *max_element(table.begin(), table.end());
        tablesize = table.size();
        bitsize = 0;
        while(table_max){
            bitsize++;
            table_max >>= 1;
        }
        assert(bitsize);
        matrix.resize(bitsize, vector<bool>(tablesize));
        zero_count.resize(bitsize, vector<long>(tablesize + 1, 0));
        for(long i = 0; i < bitsize; i++){
            for(long j = 0; j < tablesize; j++){
                matrix[i][j] = (table[j] >> (bitsize - i - 1)) & 1;
                if(not matrix[i][j]) zero_count[i][j + 1]++;
                zero_count[i][j + 1] += zero_count[i][j];
            }
            stable_sort(table.begin(), table.end(), [&](auto a, auto b){return ((a >> (bitsize - i - 1)) & 1) < ((b >> (bitsize - i - 1)) & 1);});
        }
        table_sorted = table;
    }
    
    long rank(long r, long x){
        //count x in [0, r)
        long L = 0; long R = r;//たぶんここLをlとして、引数にできる
        for(long level = 0; level < bitsize; level++){
            long same;//matrix[level][L, R)の中に、(x>>(bitsize-level-1)&1 と一致するのはいくつあるか?
            bool x_at_level = (x >> (bitsize - level - 1) & 1);
            if(x_at_level == 0){
                same = zero_count[level][R] - zero_count[level][L];
                L = zero_count[level][L]; R = L + same;
            }else{
                same = (R - zero_count[level][R]) - (L - zero_count[level][L]);
                L = zero_count[level][tablesize] + (L - zero_count[level][L]); R = L + same;
            }
        }
        return R - L;
    }
    
    long kth_min(long l, long r, long k/*0-indexed*/){
        long L = l; long R = r;
        for(long level = 0; level < bitsize; level++){
            auto [Lcount0, Lcount1] = counts(0, L, level);
            auto [count0, count1] = counts(L, R, level);
            if(k < count0){
                L = Lcount0;
                R = L + count0;
            }else{
                L = zero_count[level][tablesize] + Lcount1;
                R = L + count1;
                k -= count0;
            }
        }
        return table_sorted[L];
    }
    
    long range_freq(long l, long r, long lower, long upper){
        //count i s.t. l <= i < r and lower <= table[i] < upper
        return range_freq(l, r, upper) - range_freq(l, r, lower);
    }
    
private:
    vector<vector<bool>> matrix;
    vector<vector<long>> zero_count;//count 0 in matrix[i][0, r)
    long tablesize;
    
    pair<long,long> counts(long l, long r, long level){
        //{0の個数, 1の個数} in matrix[level][l, r)を返す
        return {zero_count[level][r] - zero_count[level][l], (r - zero_count[level][r]) - (l - zero_count[level][l])};
    }
    
    long range_freq(long l, long r, long upper){
        //count i s.t. l <= i < r and table[i] < upper
        if(upper >= (1 << bitsize)) return r - l;
        if(upper < 0) return 0;
        long res = 0;
        long L = l; long R = r;
        for(long level = 0; level < bitsize; level++){
            auto [Lcount0, Lcount1] = counts(0, L, level);
            auto [count0, count1] = counts(L, R, level);
            if(((upper >> (bitsize - level - 1)) & 1) == 0){
                //matrix[level][i] = 1　なら　必ず upper < table[i]
                L = Lcount0;
                R = L + count0;
            }else{
                //matrix[level][i] = 0　なら　必ず table[i] < upper
                res += count0;
                L = zero_count[level][tablesize] + Lcount1;
                R = L + count1;
            }
        }
        return res;
    }
};

class FenwickTree{
public:
    vector<long> table;
    long siz;
    FenwickTree(long siz) : table(siz + 1), siz(siz) {}
    long sum(long index){
        long res = 0;
        index++;//0-indexed to 1-indexed
        while(index > 0){
            res += table[index];
            index -= (index & -index);
        }
        return res;
    }
    void add(long index, long value){
        index++;//0-indexed to 1-indexed
        while(index < siz + 1){
            table[index] += value;
            index += (index & -index);
        }
    }
};

int main(){
    long N, Q; cin >> N >> Q;
    vector<long> A(N);
    for(long i = 0; i < N; i++) {
        cin >> A[i]; A[i] += 1000000000;
    }
    vector<long> acc(N + 1, 0);
    for(long i = 0; i < N; i++) acc[i+1] = acc[i] + A[i];
    WaveletMatrix wm(A);
    FenwickTree bit(N);
    vector<tuple<long,long,long,long>> query(Q);
    vector<long> res(Q);
    for(long i = 0; i < Q; i++){
        long l, r, mid;
        cin >> l >> r; l--; r--;
        mid = wm.kth_min(l, r+1, (r-l)/2);
        query[i] = {mid, l, r, i};    }
    sort(query.begin(), query.end());
    vector<pair<long,long>> AandI(N);
    for(long i = 0; i < N; i++) AandI[i] = {A[i], i};
    sort(AandI.begin(), AandI.end());
    long q = 0;
    for(long j = 0; j < N; j++){
        auto [a, i] = AandI[j];
        bit.add(i, a);
        while(q < Q and tuple<long,long,long,long>({a,0,0,0}) <= query[q] and query[q] <= tuple<long,long,long,long>({a,LONG_MAX,LONG_MAX,LONG_MAX})){
            auto [mid, l, r, res_i] = query[q];
            if(r - l == 0){
                res[res_i] = 0;
                q++;
                continue;
            }
            long sumoflessthanmid = bit.sum(r) - bit.sum(l-1) - mid;//ok
            long sumofgreaterthanmid = acc[r+1] - acc[l] - mid - sumoflessthanmid;
            long cntoflessthanmid = (r - l) / 2;//ok
            long cntofgreaterthanmid = r - l - cntoflessthanmid;//ok
            res[res_i] = (mid * cntoflessthanmid - sumoflessthanmid) + (sumofgreaterthanmid - mid * cntofgreaterthanmid);
            q++;
        }
    }
    for(long i = 0; i < Q; i++) cout << res[i] << '\n';
}