結果

問題 No.2809 Sort Query
ユーザー Aeren
提出日時 2024-07-12 22:52:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 909 ms / 2,000 ms
コード長 11,134 bytes
コンパイル時間 4,639 ms
コンパイル使用メモリ 296,352 KB
実行使用メモリ 73,344 KB
最終ジャッジ日時 2024-07-12 22:53:05
合計ジャッジ時間 57,334 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 71
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
#ifdef LOCAL
    #include "Debug.h"
#else
    #define debug_endl() 42
    #define debug(...) 42
    #define debug2(...) 42
    #define debugbin(...) 42
#endif
template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3>
struct segment_tree_base{
    static_assert(HAS_QUERY || HAS_UPDATE);
#define ifQ if constexpr(HAS_QUERY)
#define ifU if constexpr(HAS_UPDATE)
    int n, size, log;
    vector<T> data;
    vector<U> data_action;
    F1 TT; // monoid operation (always adjacent)
    T T_id; // monoid identity
    F2 UU; // monoid operation (superset, subset)
    U U_id; // monoid identity
    F3 UT; // action of U on T (superset, subset)
    // O(n)
    segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ }
    segment_tree_base &operator=(const segment_tree_base &seg){
        n = seg.n;
        size = seg.size;
        log = seg.log;
        data = seg.data;
        data_action = seg.data_action;
    }
    // O(1)
    friend void swap(segment_tree_base &x, segment_tree_base &y){
        swap(x.n, y.n);
        swap(x.size, y.size);
        swap(x.log, y.log);
        swap(x.data, y.data);
        swap(x.data_action, y.data_action);
    }
    // O(n)
    void build(int n){
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        ifQ data.assign(size << 1, T_id);
        ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id);
    }
    // O(n)
    void build(int n, T x){
        static_assert(HAS_QUERY);
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data.assign(size << 1, T_id);
        fill(data.begin() + size, data.begin() + size + n, x);
        for(auto i = size - 1; i >= 1; -- i) refresh(i);
        ifU data_action.assign(size, U_id);
    }
    // O(n)
    template<class V>
    void build(const vector<V> &a){
        static_assert(HAS_QUERY);
        n = (int)a.size();
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data.assign(size << 1, T_id);
        copy(a.begin(), a.end(), data.begin() + size);
        for(auto i = size - 1; i >= 1; -- i) refresh(i);
        ifU data_action.assign(size, U_id);
    }
    // O(n)
    void build_action(int n){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(n >= 0);
        build(n);
    }
    // O(n)
    void build_action(int n, U f){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data_action.assign(size << 1, U_id);
        fill(data_action.begin() + size, data_action.begin() + size + n, f);
    }
    // O(n)
    template<class V>
    void build_action(const vector<V> &a){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        n = (int)a.size();
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data_action.assign(size << 1, U_id);
        copy(a.begin(), a.end(), data_action.begin() + size);
    }
    // O(1)
    void refresh(int u){
        static_assert(HAS_QUERY);
        data[u] = TT(data[u << 1], data[u << 1 | 1]);
    }
    // O(1)
    void apply(int u, U f){
        static_assert(HAS_UPDATE);
        ifQ data[u] = UT(f, data[u]);
        if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]);
    }
    // O(1)
    void push(int u){
        static_assert(HAS_UPDATE);
        apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]);
        data_action[u] = U_id;
    }
    // O(log(n)) if HAS_UPDATE, O(1) otherwise.
    T query(int p){
        static_assert(HAS_QUERY);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        return data[p];
    }
    // O(log(n))
    U query_action(int p){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        return data_action[p];
    }
    // O(log(n))
    T query(int ql, int qr){
        static_assert(HAS_QUERY);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return T_id;
        ql += size, qr += size;
        ifU for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        T res_left = T_id, res_right = T_id;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) res_left = TT(res_left, data[ql ++]);
            if(qr & 1) res_right = TT(data[-- qr], res_right);
        }
        return TT(res_left, res_right);
    }
    // O(1)
    T query_all() const{
        static_assert(HAS_QUERY);
        return data[1];
    }
    // O(n)
    vector<T> to_array(){
        static_assert(HAS_QUERY);
        ifU for(auto u = 1; u < size; ++ u) push(u);
        return vector<T>(data.begin() + size, data.begin() + size + n);
    }
    // O(n)
    vector<U> to_array_of_updates(){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        for(auto u = 1; u < size; ++ u) push(u);
        return vector<U>(data_action.begin() + size, data_action.begin() + size + n);
    }
    // O(log(n))
    void set(int p, T x){
        static_assert(HAS_QUERY);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        data[p] = x;
        for(auto i = 1; i <= log; ++ i) refresh(p >> i);
    }
    // O(log(n))
    void set_action(int p, U f){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        for(auto i = log; i >= 1; -- i) push(p >> i);
        data_action[p] = f;
    }
    // O(log(n))
    void update(int p, U f){
        static_assert(HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        for(auto i = log; i >= 1; -- i) push(p >> i);
        ifQ{
            data[p] = UT(f, data[p]);
            for(auto i = 1; i <= log; ++ i) refresh(p >> i);
        }
        else data_action[p] = UU(f, data_action[p]);
    }
    // O(log(n))
    void update(int ql, int qr, U f){
        static_assert(HAS_UPDATE);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return;
        ql += size, qr += size;
        for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        int _ql = ql, _qr = qr;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) apply(ql ++, f);
            if(qr & 1) apply(-- qr, f);
        }
        ql = _ql, qr = _qr;
        ifQ for(auto i = 1; i <= log; ++ i){
            if(ql >> i << i != ql) refresh(ql >> i);
            if(qr >> i << i != qr) refresh(qr >> i);
        }
    }
    void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
        static_assert(HAS_QUERY && HAS_UPDATE);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return;
        ql += size, qr += size;
        for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        auto recurse = [&](auto self, int u)->void{
            if(exit_rule(data[u])) return;
            if(enter_rule(data[u])){
                apply(u, update_rule(data[u]));
                return;
            }
            push(u);
            self(self, u << 1), self(self, u << 1 | 1);
            refresh(u);
        };
        int _ql = ql, _qr = qr;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) recurse(recurse, ql ++);
            if(qr & 1) recurse(recurse, -- qr);
        }
        ql = _ql, qr = _qr;
        for(auto i = 1; i <= log; ++ i){
            if(ql >> i << i != ql) refresh(ql >> i);
            if(qr >> i << i != qr) refresh(qr >> i);
        }
    }
    // pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F
    // Returns max r with T
    // O(log(n))
    int max_pref(int ql, auto pred){
        static_assert(HAS_QUERY);
        assert(0 <= ql && ql <= n && pred(T_id));
        if(ql == n) return n;
        ql += size;
        ifU for(auto i = log; i >= 1; -- i) push(ql >> i);
        T sum = T_id;
        do{
            while(~ql & 1) ql >>= 1;
            if(!pred(TT(sum, data[ql]))){
                while(ql < size){
                    ifU push(ql);
                    ql = ql << 1;
                    if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]);
                }
                return ql - size;
            }
            sum = TT(sum, data[ql]);
            ++ ql;
        }while((ql & -ql) != ql);
        return n;
    }
    // pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T
    // Returns min l with T
    // O(log(n))
    int max_suff(int qr, auto pred){
        static_assert(HAS_QUERY);
        assert(0 <= qr && qr <= n && pred(T_id));
        if(qr == 0) return 0;
        qr += size;
        ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i);
        T sum = T_id;
        do{
            -- qr;
            while(qr > 1 && qr & 1) qr >>= 1;
            if(!pred(TT(data[qr], sum))){
                while(qr < size){
                    ifU push(qr);
                    qr = qr << 1 | 1;
                    if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum);
                }
                return qr + 1 - size;
            }
            sum = TT(data[qr], sum);
        }while((qr & -qr) != qr);
        return 0;
    }
    template<class output_stream>
    friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){
        out << "{";
        for(auto i = 0; i < seg.n; ++ i){
            ifQ out << seg.query(i);
            else out << seg.query_action(i);
            if(i != seg.n - 1) out << ", ";
        }
        return out << '}';
    }
#undef ifQ
#undef ifU
};
// Supports query
template<class T, class F>
auto make_Q_segment_tree(F TT, T T_id){
    using U = int;
    auto _UU = [&](U, U)->U{ return U{}; };
    auto _UT = [&](U, T)->T{ return T{}; };
    return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT);
}
// Supports update
template<class U, class F>
auto make_U_segment_tree(F UU, U U_id){
    using T = int;
    auto _TT = [&](T, T)->T{ return T{}; };
    auto _UT = [&](U, T)->T{ return T{}; };
    return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT);
}
// Supports query and update
template<class T, class U, class F1, class F2, class F3>
auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){
    return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(ios::badbit | ios::failbit);
    int n, qn;
    cin >> n >> qn;
    vector<long long> a(n);
    copy_n(istream_iterator<long long>(cin), n, a.begin());
    vector<pair<long long, int>> cmpr;
    for(auto i = 0; i < n; ++ i){
        cmpr.push_back({a[i], i});
    }
    vector<array<long long, 3>> q(qn);
    for(auto i = n; auto &[type, p, x]: q){
        cin >> type;
        if(type != 2){
            cin >> p, -- p;
            if(type == 1){
                cin >> x;
                cmpr.push_back({x, i ++});
            }
        }
    }
    ranges::sort(cmpr);
    cmpr.erase(ranges::unique(cmpr).begin(), cmpr.end());
    using T = pair<int, long long>; // cnt, maxv
    T T_id{0, -1};
    auto TT = [&](const T &x, const T &y)->T{
        return {x.first + y.first, max(x.second, y.second)};
    };
    auto seg = make_Q_segment_tree(TT, T_id);
    auto index = [&](long long x, int i)->int{
        return ranges::lower_bound(cmpr, pair{x, i}) - cmpr.begin();
    };
    seg.build((int)cmpr.size(), T_id);
    map<int, int> lazy;
    for(auto i = 0; i < n; ++ i){
        lazy[i] = index(a[i], i);
    }
    for(int i = n; auto [type, p, x]: q){
        if(type == 1){
            lazy[p] = index(x, i ++);
        }
        else if(type == 2){
            static vector<int> update;
            update.clear();
            for(auto [p, v]: lazy | ranges::views::reverse){
                auto w = seg.max_pref(0, [&](auto pref){ return pref.first <= p; });
                if(w < (int)cmpr.size()){
                    seg.set(w, T_id);
                }
                update.push_back(v);
            }
            ranges::sort(update);
            for(auto v: update){
                seg.set(v, T{1, cmpr[v].first});
            }
            lazy.clear();
        }
        else{
            if(lazy.contains(p)){
                cout << cmpr[lazy[p]].first << "\n";
            }
            else{
                auto x = seg.max_pref(0, [&](auto pref){ return pref.first <= p; });
                cout << seg.query(x).second << "\n";
            }
        }
    }
    return 0;
}
/*
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0