結果

問題 No.924 紲星
ユーザー ooaiu
提出日時 2025-08-31 20:59:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,351 bytes
コンパイル時間 3,745 ms
コンパイル使用メモリ 294,288 KB
実行使用メモリ 31,044 KB
最終ジャッジ日時 2025-08-31 20:59:43
合計ジャッジ時間 10,384 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/segtree>
template <class T = long long>
class Compressor {
   private:
    std::vector<T> cc;
    bool sorted;

   public:
    Compressor() : sorted(false) {}
    Compressor(const std::vector<T>& a) {
        for (auto x : a) cc.push_back(x);
        build();
    }
    void add(const T& x) {
        cc.push_back(x);
        sorted = false;
    }
    T operator[](int i) const {
        assert(sorted);
        return cc[i];
    }
    int operator()(const T& x) const {
        assert(sorted);
        return lower_bound(begin(cc), end(cc), x) - begin(cc);
    }
    int size() const {
        assert(sorted);
        return cc.size();
    }
    void build() {
        sort(begin(cc), end(cc));
        cc.erase(unique(begin(cc), end(cc)), end(cc));
        sorted = true;
    }
    static std::vector<int> compressed(const std::vector<T>& a) {
        Compressor c(a);
        std::vector<int> res(a.size());
        for(int i = 0; i < (int)a.size(); i++) res[i] = c(a[i]);
        return res;
    }
};

template <class T>
class FixedSet {
    struct S {
        T sum;
        int count;
    };
    static S op(S a, S b) { return S{a.sum + b.sum, a.count + b.count}; }
    static S e() { return S{T{}, 0}; }
    using STree = atcoder::segtree<S, op, e>;
    STree d;
    Compressor<T> cc;
    size_t sz;
    int index(const T& x) {
        int p = cc(x);
        assert(0 <= p && p < cc.size() && cc[p] == x);
        return p;
    }

   public:
    FixedSet() {}
    FixedSet(const std::vector<T>& A) {
        cc = Compressor<T>(A);
        d = STree(cc.size());
        sz = 0;
    }
    void add(const T& x, int c = 1) {
        int p = index(x);
        S pv = d.get(p);
        sz -= pv.count;
        int cnt = std::max(0, pv.count + c);
        d.set(p, S{x * cnt, cnt});
        sz += cnt;
    }
    T top_k_sum(int k) {
        if (k == 0) return T{};
        assert(k <= (int)size());
        const auto f = [&](S x) { return x.count < k; };
        int l = d.min_left(cc.size(), f) - 1;
        S res = d.prod(l, cc.size());
        T sum = res.sum - cc[l] * (res.count - k);
        return sum;
    }
    T bottom_k_sum(int k) {
        if (k == 0) return T{};
        assert(k <= (int)size());
        const auto f = [&](S x) { return x.count < k; };
        int r = d.max_right(0, f);
        S res = d.prod(0, r);
        T sum = res.sum + cc[r] * (k - res.count);
        return sum;
    }
    T kth_smallest(int k) {
        assert(0 < k && k <= sz);
        const auto f = [&](S x) { return x.count < k; };
        int r = d.max_right(0, f);
        return cc[r];
    }
    T kth_largest(int k) {
        return kth_smallest(sz - k + 1);
    }
    size_t size() const { return sz; }
    bool empty() const { return size() == 0; }
    int count(const T& x) {
        int pos = index(x);
        return d.get(pos).count;
    }
    T sum() const { return d.all_prod().sum; }
};

using namespace std;
int N, Q;
const int maxn = 2 << 17;
int A[maxn], L[maxn], R[maxn];
long long S[maxn];
int ord[maxn];
long long ans[maxn];
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        S[i + 1] = S[i] + A[i];
    }
    const int B = std::max<int>(1, 1.0 * N / std::max<double>(1.0, std::sqrt(Q) * 2.0 / 3.0));
    for (int i = 0; i < Q; i++) {
        ord[i] = i;
        cin >> L[i] >> R[i];
        L[i]--;
    }
    sort(ord, ord + Q, [&](int i, int j) -> bool {
        int iblock = L[i] / B, jblock = L[j] / B;
        if (iblock != jblock) return iblock < jblock;
        if (iblock & 1) return R[i] < R[j];
        return R[i] > R[j];
    });
    FixedSet<long long> st(vector<long long>{A, A + N});
    int nl = 0, nr = 0;
    for (int qi = 0; qi < Q; qi++) {
        int i = ord[qi];
        while (nl > L[i]) st.add(A[--nl]);
        while (nr < R[i]) st.add(A[nr++]);
        while (nl < L[i]) st.add(A[nl++], -1);
        while (nr > R[i]) st.add(A[--nr], -1);
        int W = R[i] - L[i];
        int m = (W + 1) / 2;
        long long mid = st.kth_largest(m);
        long long top = st.top_k_sum(W - m);
        long long bot = (S[R[i]] - S[L[i]] - top);
        ans[i] = top - mid * (W - m) + mid * m - bot;
    }
    for (int i = 0; i < Q; i++) cout << ans[i] << "\n";
}
0