結果

問題 No.924 紲星
コンテスト
ユーザー rogi52
提出日時 2025-10-17 10:19:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,473 ms / 4,000 ms
コード長 11,622 bytes
コンパイル時間 4,707 ms
コンパイル使用メモリ 317,832 KB
実行使用メモリ 277,804 KB
最終ジャッジ日時 2025-10-17 10:20:24
合計ジャッジ時間 24,003 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "/Users/korogi/Desktop/cp-cpp/template.hpp"
#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
using f32 = double;
using f64 = long double;
using f128 = __float128;

#define DMP(x) cout << "[" << __LINE__ << "]" << " " << #x << ":" << " " << x << endl;

#define FOR1(n)          for(int _ =  0 , n_ = (n); _ < n_; _++)
#define FOR2(i, n)       for(int i =  0 , n_ = (n); i < n_; i++)
#define FOR3(i, s, t)    for(int i = (s), t_ = (t); i < t_; i++)
#define FOR4(i, s, t, d) for(int i = (s), t_ = (t), d_ = (d); i < t_; i += d_)
#define OVERLOAD4(a, b, c, d, e, ...) e
#define FOR(...) OVERLOAD4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define REV1(n)          for(int _ = (n) - 1; _ >=  0 ; _--)
#define REV2(i, n)       for(int i = (n) - 1; i >=  0 ; i--)
#define REV3(i, s, t)    for(int i = (t) - 1, s_ = (s); i >= s_; i--)
#define REV4(i, s, t, d) for(int i = (t) - 1, s_ = (s), d_ = (d); i >= s_; i -= d_)
#define OVERLOAD3(a, b, c, d, ...) d
#define REV(...) OVERLOAD4(__VA_ARGS__, REV4, REV3, REV2, REV1)(__VA_ARGS__)

#define FOR_SUBSET(T, S) for(int S_ = (S), T = S_; T >= 0; T = (T == 0 ? -1 : (T - 1) & S_))

#define MULTI for(int testcase_ = in(), testcase = 0; testcase < testcase_; testcase++) [&]

template < class T > using heap_max = priority_queue< T, vector< T >, less< T > >;
template < class T > using heap_min = priority_queue< T, vector< T >, greater< T >>;

template < class T, class U > bool chmin(T& a, const U& b) { return a > b ? a = b, 1 : 0; }
template < class T, class U > bool chmax(T& a, const U& b) { return a < b ? a = b, 1 : 0; }

i64 floor_div(const i64 n, const i64 d) { assert(d != 0); return n / d - ((n ^ d) <  0 && n % d != 0); }
i64  ceil_div(const i64 n, const i64 d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d != 0); }

template < class T, class F > T bin_search(T ok, T ng, F check) { while(abs(ok - ng) > 1) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }
template < class T, class F > T bin_search_real(T ok, T ng, F check, int step = 100) { FOR(step) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }

template < class T, class U > T accum(const vector< U >& a) { return accumulate(a.begin(), a.end(), T(0)); }
template < class T > pair< T, int > min(const vector< T >& a) { auto itr = min_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
template < class T > pair< T, int > max(const vector< T >& a) { auto itr = max_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
template < class T > void sort(vector< T >& a) { sort(a.begin(), a.end()); }
template < class T > void rsort(vector< T >& a) { sort(a.rbegin(), a.rend()); }
template < class T > void reverse(vector< T >& a) { reverse(a.begin(), a.end()); }
void sort(string& s) { sort(s.begin(), s.end()); }
void rsort(string& s) { sort(s.rbegin(), s.rend()); }
void reverse(string& s) { reverse(s.begin(), s.end()); }
template < class T, class Cmp > void sort(vector< T >& a, Cmp cmp) { sort(a.begin(), a.end(), cmp); }
template < class T > int LB(vector< T >& a, T x) { return distance(a.begin(), lower_bound(a.begin(), a.end(), x)); }
template < class T > int UB(vector< T >& a, T x) { return distance(a.begin(), upper_bound(a.begin(), a.end(), x)); }
template < class T > void unique(vector< T >& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
vector<int> iota(int n) { vector<int> a(n); iota(a.begin(), a.end(), 0); return a; }

istream& operator >> (istream& is, i128& x) {
    string s; is >> s;
    int m = (s[0] == '-');
    x = 0;
    FOR(i, m, ssize(s)) x = x * 10 + (s[i] - '0');
    if(m) x *= -1;
    return is;
}
ostream& operator << (ostream& os, const i128& x) {
    if(x == 0) return os << '0';
    i128 y = x; if(y < 0) { os << '-'; y *= -1; }
    vector<int> ny;
    while(y) ny.push_back(y % 10), y /= 10;
    REV(i, ssize(ny)) os << ny[i];
    return os;
}
namespace scan {
struct x0 { template < class T > operator T() { T x; cin >> x; return x; } };
struct x1 { int n; x1(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > a(n); for(T& x : a) cin >> x; return a; } };
struct x2 { int h, w; x2(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& a : m) for(T& x : a) cin >> x; return m; } };
struct cppio { cppio() { cin.tie(0); ios::sync_with_stdio(0); } } cppio_instance;
}
scan::x0 in() { return scan::x0(); }
scan::x1 in(int n) { return scan::x1(n); }
scan::x2 in(int h, int w) { return scan::x2(h, w); }

template < class T > ostream& operator << (ostream& os, const vector< T >& a) {
    const int n = a.size();
    FOR(i, n) { os << a[i]; if(i + 1 != n) os << ' '; }
    return os;
}
template < class T > int print_n(const vector< T >& a) { for(const T& x : a) cout << x << '\n'; return 0; }
int print() { cout << '\n'; return 0; }
template < class Head, class... Tail > int print(Head&& h, Tail&&... t) { cout << h; if(sizeof...(Tail)) cout << ' '; return print(forward<Tail>(t)...); }
namespace printer {
    void prec(int n) { cout << fixed << setprecision(n); }
    void flush() { cout.flush(); }
}

constexpr pair<int, int> dir4[] = {{-1, 0}, {0, -1}, {+1, 0}, {0, +1}};

vector<int>& operator ++ (vector<int>& a) { for(auto& e : a) e++; return a; }
vector<int>& operator -- (vector<int>& a) { for(auto& e : a) e--; return a; }
vector<int>  operator ++ (vector<int>& a, int) { vector<int> b = a; ++a; return b; }
vector<int>  operator -- (vector<int>& a, int) { vector<int> b = a; --a; return b; }

template < class T > vector<pair< T, int>> RLE(const vector< T >& a) { vector<pair< T, int>> v; for(const T& x : a) { if(not v.empty() and v.back().first == x) v.back().second++; else v.emplace_back(x, 1); } return v; }
vector<pair<char, int>> RLE(const string& s) { vector<pair<char, int>> v; for(const char& c : s) { if(not v.empty() and v.back().first == c) v.back().second++; else v.emplace_back(c, 1); } return v; }
template < class String, class Same > vector<String> RLE(const String& a, const Same same) { vector<String> v; for(const auto& x : a) { if(not v.empty() and same(v.back().back(), x)) v.back().push_back(x); else v.push_back({x}); } return v; }

int YESNO(bool yes) { return print(yes ? "YES" : "NO"); }
int YesNo(bool yes) { return print(yes ? "Yes" : "No"); }

constexpr i32 INF32 = 1e9;
constexpr i64 INF64 = 1e18;
#line 3 "/Users/korogi/Desktop/cp-cpp/ds/persistent_segtree.hpp"

template < class Monoid > struct per_segtree {
    using M = Monoid;
    using V = typename M::value_type;
    struct node;
    using ptr = node*;
    struct node {
        V v;
        ptr l, r;
        node() {}
        node(const V& v) : v(v), l(nullptr), r(nullptr) {}
        node(const V& v, const ptr& l, const ptr& r) : v(v), l(l), r(r) {}
    };

    int n;
    per_segtree() {}
    per_segtree(int n) : n(n) {}
    
    ptr build() { return build(M::e()); }
    ptr build(const V& v) { return build(vector(n, v)); }
    ptr build(const vector< V >& v) {
        assert(ssize(v) == n);
        return build(0, n, v);
    }

    // a[i] <- v
    ptr set(ptr a, int i, const V& v) {
        assert(0 <= i and i < n);
        return set(i, v, a, 0, n);
    }
    // a[l, r)
    V v(ptr a, int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        return prod(l, r, a, 0, n);
    }
    // a[i]
    V v(ptr a, int i) {
        assert(0 <= i and i < n);
        return prod(i, i + 1, a, 0, n);
    }
    // a[0, n)
    V av(ptr a) {
        return a->v;
    }
    // a[i] <- op(a[i], v)
    ptr o(ptr a, int i, const V& v) {
        assert(0 <= i and i < n);
        return apply(i, v, a, 0, n);
    }

  private:
    ptr merge(ptr l, ptr r) {
        return new node(M::op(l->v, r->v), l, r);
    }
    ptr build(int l, int r, const vector<V>& v) {
        if(l + 1 == r) return new node(v[l]);
        const int m = (l + r) / 2;
        return merge(build(l, m, v), build(m, r, v));
    }
    ptr set(int i, const V& v, ptr p, int l, int r) {
        if(r <= i or i + 1 <= l) return p;
        if(i <= l and r <= i + 1) return new node(v);
        const int m = (l + r) / 2;
        return merge(set(i, v, p->l, l, m), set(i, v, p->r, m, r));
    }
    ptr apply(int i, const V& v, ptr p, int l, int r) {
        if(r <= i or i + 1 <= l) return p;
        if(i <= l and r <= i + 1) return new node(M::op(p->v, v));
        const int m = (l + r) / 2;
        return merge(apply(i, v, p->l, l, m), apply(i, v, p->r, m, r));
    }
    V prod(int a, int b, ptr p, int l, int r) {
        if(r <= a or b <= l) return M::e();
        if(a <= l and r <= b) return p->v;
        const int m = (l + r) / 2;
        return M::op(prod(a, b, p->l, l, m), prod(a, b, p->r, m, r));
    }
};
#line 3 "/Users/korogi/Desktop/cp-cpp/ds/rect_sum.hpp"

// 点とその重み: オフライン
// 長方形: オンライン
template < class Index, class Monoid > struct rect_sum {
    using I = Index;
    using M = Monoid;
    using V = typename M::value_type;
    per_segtree< M > pst;
    vector<typename per_segtree< M >::ptr> seg;
    vector< I > X, Y;
    vector< V > W;

    rect_sum(const vector< I >& x, const vector< I >& y, const vector< V >& w) {
        const int n = ssize(x);
        assert(ssize(y) == n);
        assert(ssize(w) == n);
        vector<int> ord = iota(n);
        sort(ord, [&](int i, int j) { return y[i] < y[j]; });
        for(int i : ord) {
            X.push_back(x[i]);
            Y.push_back(y[i]);
            W.push_back(w[i]);
        }
        sort(ord, [&](int i, int j) { return X[i] < X[j]; });
        pst = per_segtree< M >(n);
        seg.resize(n + 1);
        seg[0] = pst.build();
        vector< I > X2;
        FOR(t, n) {
            const int i = ord[t];
            seg[t + 1] = pst.o(seg[t], i, W[i]);
            X2.push_back(X[i]);
        }
        X = move(X2);
    }

    // [x1, x2) * [y1, y2)
    V sum(I xL, I xR, I yL, I yR) {
        assert(xL <= xR);
        assert(yL <= yR);
        const int l = LB(Y, yL), r = LB(Y, yR);
        return pst.v(seg[LB(X, xR)], l, r) - pst.v(seg[LB(X, xL)], l, r);
    }
};
#line 3 "/Users/korogi/Desktop/cp-cpp/alg/sum.hpp"

namespace alg {
template < class T > struct sum {
    using value_type = T;
    static constexpr T op(const T& a, const T& b) { return a + b; }
    static constexpr T e() { return T(0); }
    static constexpr T inv(const T& a) { return -a; }
    static constexpr bool comm() { return true; }
};
}
#line 5 "b.cpp"

int main() {
    int N = in(), Q = in();
    vector<int> A = in(N);
    vector<i64> KC(N, i64(1)), KS(N);
    FOR(i, N) KS[i] = A[i];
    rect_sum<int, alg::sum<i64>> C(iota(N), A, KC);
    rect_sum<int, alg::sum<i64>> S(iota(N), A, KS);
    using ptr = decltype(C.pst)::ptr;
    auto kth = [&](auto kth, ptr pl, ptr pr, int l, int r, int k) -> int {
        if(l + 1 == r) return l;
        const int m = (l + r) / 2;
        const int c = pr->l->v - pl->l->v;
        if(k < c) {
            return kth(kth, pl->l, pr->l, l, m, k);
        } else {
            return kth(kth, pl->r, pr->r, m, r, k - c);
        }
    };

    const int LV = -1e9, RV = +1e9 + 1;
    FOR(Q) {
        int L = in(), R = in(); L--;
        const i64 X = C.Y[kth(kth, C.seg[L], C.seg[R], 0, N, (R - L) / 2)];
        i64 ans = 0;
        ans += S.sum(L, R, X, RV) - X * C.sum(L, R, X, RV);
        ans += C.sum(L, R, LV, X) * X - S.sum(L, R, LV, X);
        print(ans);
    }
}
0