結果

問題 No.924 紲星
コンテスト
ユーザー ferin
提出日時 2019-11-08 23:44:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 594 ms / 4,000 ms
コード長 8,740 bytes
コンパイル時間 2,155 ms
コンパイル使用メモリ 185,104 KB
実行使用メモリ 39,388 KB
最終ジャッジ日時 2024-09-15 02:47:19
合計ジャッジ時間 8,661 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

template<int N>
struct FID {
    static const int bucket = 512, block = 16;
    static char popcount[];
    int n;
    array<int, N/bucket+10> large;
    array<unsigned short, N/block+10> small, bs;

    // 初期化 O(2^16 + n)
    FID(){}
    FID(int n, array<bool, N> s) : n(n) {
        if(!popcount[1]) REP(i, 1<<block) popcount[i] = __builtin_popcount(i);

        bs[0] = small[0] = 0;
        large[0] = 0;
        REP(i, n) {
            if(i%block == 0) {
                bs[i/block+1] = 0;
                if(i%bucket == 0) {
                    large[i/bucket+1] = large[i/bucket];
                    small[i/block+1] = small[i/block] = 0;
                }
                else small[i/block+1] = small[i/block];
            }
            bs[i/block] |= short(s[i])<<(i%block);
            small[i/block+1]  += s[i];
            large[i/bucket+1] += s[i];
        }
        if(n%bucket == 0) small[n/block] = 0;
    }

    // [0,r)のvalの個数 O(1)
    int rank(bool val, int r) {
        if(val) {
            char bitnum = popcount[bs[r/block]&((1<<(r%block))-1)];
            return large[r/bucket] + small[r/block] + bitnum;
        }
        return r-rank(1,r); 
    }
    // [l,r)のvalの個数 O(1)
    int rank(bool val, int l, int r) { return rank(val,r)-rank(val,l); }

    // i個目の値valの位置 O(logn)
    int select(bool val, int i) {
        if(i < 0 || rank(val,n) <= i) return -1;
        i++;
        int lb = 0, ub = n;
        while(ub-lb>1) {
            int mid = (lb+ub)>>1;
            if(rank(val,mid) >= i) ub = mid;
            else lb = mid;
        }
        return ub-1;
    }
    int select(bool val, int i, int l) { return select(val,i+rank(val,l)); }

    // bit列のi番目 O(1)
    bool operator[](int i) { return bs[i/block]>>(i%block)&1; }
};
template<int N> char FID<N>::popcount[1<<FID<N>::block];

template<class T, int N, int LEVEL>
struct wavelet {
    int n;
    array<int, LEVEL> zs;
    array<FID<N>, LEVEL> dat;

    wavelet(int n, array<T, N> seq) : n(n) {
        array<T, N> f, l, r;
        array<bool, N> b;
        copy(seq.begin(), seq.begin()+n, f.begin());
        REP(d, LEVEL) {
            int lh = 0, rh = 0;
            REP(i, n) {
                bool k = f[i]&1<<(LEVEL-d-1);
                if(k) r[rh++] = f[i];
                else l[lh++] = f[i];
                b[i] = k;
            }
            dat[d] = FID<N>(n,b);
            zs[d] = lh;
            swap(l,f);
            copy(r.begin(), r.begin()+rh, f.begin()+lh);
        }
    }

    // i番目の要素をgetする
    T get(int i) {
        T ret = 0;
        REP(d, LEVEL) {
            ret <<= 1;
            bool b = dat[d][i];
            ret |= b;
            i = dat[d].rank(b,i) + b*zs[d]; // (b?zs[d]:0)
        }
        return ret;
    }
    T operator[](int i) { return get(i); }

    // [l,r)にvalが何個あるか O(LEVEL)
    int rank(T val, int l, int r) {
        REP(d, LEVEL) {
            bool b = val&1<<(LEVEL-d-1);
            l = dat[d].rank(b,l) + b*zs[d];
            r = dat[d].rank(b,r) + b*zs[d];
        }
        return r-l;
    }

    // k番目のvalの位置
    int select(T val, int k) {
        array<int, LEVEL> ls, rs;
        int l=0, r=n;
        REP(d, LEVEL) {
            ls[d] = l, rs[d] = r;
            bool b = val&1<<(LEVEL-d-1);
            l = dat[d].rank(b, l) + b*zs[d];
            r = dat[d].rank(b, r) + b*zs[d];
        }
        for(int d=LEVEL-1; d>=0; --d) {
            bool b = val&1<<(LEVEL-d-1);
            k = dat[d].select(b,k,ls[d]);
            if(k >= rs[d] || k < 0) return -1;
        }
        return k;
    }
    // [l,n)でk番目のval
    int select(T val, int k, int l) { return select(val, k+rank(val,0,l)); }

    // [l,r)で小さい(大きい)方からk番目(0-index)の要素を返す
    template<bool ascending=true>
    T kthnumber(int l, int r, int k) {
        if(r-l <= k || k < 0) return -1;
        T ret = 0;
        if(ascending) {
            REP(d, LEVEL) {
                int lc = dat[d].rank(0,l), rc = dat[d].rank(0,r);
                if(rc-lc > k) {
                    l = lc;
                    r = rc;
                } else {
                    k -= rc-lc;
                    l = l - lc + zs[d];
                    r = r - rc + zs[d];
                    ret |= 1ULL<<(LEVEL-d-1);
                }
            }
        } else {
            REP(d, LEVEL) {
                int lc = dat[d].rank(1,l), rc = dat[d].rank(1,r);
                if(rc-lc > k) {
                    l = lc+zs[d];
                    r = rc+zs[d];
                    ret |= 1ULL<<(LEVEL-d-1);
                } else {
                    k -= rc-lc;
                    l -= lc;
                    r -= rc;
                }
            }
        }
        return ret;
    }

    // [l,r)でx未満の要素数
    int rank_lt(int l, int r, T x) {
        int ret = 0;
        REP(d, LEVEL) {
            int lnum = dat[d].rank(1,l), rnum = dat[d].rank(1,r);
            if(x&1<<(LEVEL-d-1)) {
                ret += r-l-(rnum-lnum);
                l = zs[d] + lnum;
                r = zs[d] + rnum;
            } else {
                l -= lnum;
                r -= rnum;
            }
            if(l > r) assert(false);
        }
        return ret;
    }
    // [l,r)中でx以上y未満の要素
    int rangefreq(int l, int r, T x, T y) { 
        return rank_lt(l,r,y) - rank_lt(l,r,x);
    }
};

// 根が1 !!!!!
template<typename Monoid>
struct segtree {
    using T = typename Monoid::T;
    int n;
    vector<T> dat;

    segtree(int n_) {
        n = 1;
        while(n < n_) n <<= 1;
        dat.assign(n*2, Monoid::id());
    }
    void build(vector<T> v) {
        REP(i, v.size()) dat[i+n] = v[i];
        for(int i=n-1; i>0; --i) dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);
    }

    T query(int a, int b) {
        T l = Monoid::id(), r = Monoid::id();
        for(a+=n, b+=n; a<b; a>>=1, b>>=1) {
            if(a&1) l = Monoid::op(l, dat[a++]);
            if(b&1) r = Monoid::op(dat[--b], r);
        }
        return Monoid::op(l, r);
    }
    void update(int i, T v) {
        i += n;
        dat[i] = v;
        while(i >>= 1) {
            dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);
        }
    }

    friend ostream &operator <<(ostream& out,const segtree<Monoid>& seg){
        out << "---------------------" << endl;
        int cnt = 1;
        for(int i=1; i<=seg.n; i*=2) {
            REP(j, i) {
                out << seg.dat[cnt] << " ";
                cnt++;
            }
            out << endl;
        }
        out << "---------------------" << endl;
        return out;
    }
};

template<typename Tp>
struct sum_monoid {
    using T = Tp;
    static constexpr Tp id() { return 0; }
    static Tp op(const Tp &a, const Tp &b) { return a+b; }
};

int main(void) {
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n), l(q), r(q);
    REP(i, n) cin >> a[i];
    REP(i, q) cin >> l[i] >> r[i], l[i]--, r[i]--;

    array<int, 200010> seq;
    REP(i, n) seq[i] = a[i] + 1000000000;
    wavelet<int, 200010, 32> wave(n, seq);

    vector<ll> mid(q);
    REP(i, q) mid[i] = wave.kthnumber(l[i], r[i]+1, (r[i]-l[i]+1)/2) - 1000000000;

    dump(mid);
    
    vector<ll> ord(q);
    iota(ALL(ord), 0);
    sort(ALL(ord), [&](ll l, ll r){
        return mid[l] < mid[r];
    });

    dump(ord);

    vector<PII> va(n);
    REP(i, n) va[i] = PII(a[i], i);
    sort(ALL(va));

    ll idx = 0;
    vector<ll> ans(q);
    segtree<sum_monoid<ll>> seg1(n), cnt1(n), seg2(n), cnt2(n);
    seg2.build(a);
    cnt2.build(vector<ll>(n, 1));
    for(auto i: ord) {
        // mid[i] 未満のやつを seg2 から seg1 に移す
        while(idx<n && va[idx].first<mid[i]) {
            ll j = va[idx].second;
            seg2.update(j, 0);
            cnt2.update(j, 0);
            seg1.update(j, a[j]);
            cnt1.update(j, 1);
            idx++;
        }

        ans[i] += seg2.query(l[i], r[i]+1) - mid[i] * cnt2.query(l[i], r[i]+1);
        ans[i] += mid[i] * cnt1.query(l[i], r[i]+1) - seg1.query(l[i], r[i]+1);
    }

    for(auto i: ans) cout << i << "\n";
    cout << flush;

    return 0;
}
0