#993957 (C++17) No.2809 Sort Query

• 問題: No.2809 Sort Query
• ユーザー: Nachia
• 提出日時: 2024-07-12 21:17:01
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,156 ms / 2,000 ms
• コード長: 14,937 bytes
• コンパイル時間: 1,235 ms
• コンパイル使用メモリ: 111,400 KB
• 実行使用メモリ: 36,156 KB
• 最終ジャッジ日時: 2024-07-12 21:18:21
• 合計ジャッジ時間: 62,844 ms
• ジャッジサーバーID （参考情報）: judge6 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	675 ms; 34,880 KB
testcase_02	AC	679 ms; 34,404 KB
testcase_03	AC	712 ms; 34,276 KB
testcase_04	AC	678 ms; 35,236 KB
testcase_05	AC	716 ms; 35,600 KB
testcase_06	AC	669 ms; 35,904 KB
testcase_07	AC	710 ms; 34,728 KB
testcase_08	AC	677 ms; 35,712 KB
testcase_09	AC	681 ms; 34,412 KB
testcase_10	AC	709 ms; 36,112 KB
testcase_11	AC	1,112 ms; 35,124 KB
testcase_12	AC	1,063 ms; 34,816 KB
testcase_13	AC	1,021 ms; 34,472 KB
testcase_14	AC	1,038 ms; 35,056 KB
testcase_15	AC	989 ms; 35,708 KB
testcase_16	AC	1,030 ms; 34,948 KB
testcase_17	AC	1,011 ms; 34,888 KB
testcase_18	AC	1,032 ms; 35,444 KB
testcase_19	AC	1,035 ms; 34,528 KB
testcase_20	AC	1,118 ms; 34,596 KB
testcase_21	AC	1,148 ms; 34,412 KB
testcase_22	AC	1,149 ms; 35,408 KB
testcase_23	AC	1,156 ms; 34,720 KB
testcase_24	AC	1,104 ms; 34,588 KB
testcase_25	AC	1,126 ms; 35,432 KB
testcase_26	AC	889 ms; 34,552 KB
testcase_27	AC	841 ms; 35,544 KB
testcase_28	AC	808 ms; 34,464 KB
testcase_29	AC	889 ms; 35,652 KB
testcase_30	AC	892 ms; 34,948 KB
testcase_31	AC	717 ms; 35,116 KB
testcase_32	AC	733 ms; 35,924 KB
testcase_33	AC	766 ms; 34,796 KB
testcase_34	AC	746 ms; 36,156 KB
testcase_35	AC	737 ms; 34,884 KB
testcase_36	AC	991 ms; 34,532 KB
testcase_37	AC	957 ms; 36,052 KB
testcase_38	AC	939 ms; 34,560 KB
testcase_39	AC	946 ms; 34,728 KB
testcase_40	AC	986 ms; 35,860 KB
testcase_41	AC	694 ms; 34,400 KB
testcase_42	AC	761 ms; 34,960 KB
testcase_43	AC	712 ms; 34,668 KB
testcase_44	AC	688 ms; 35,060 KB
testcase_45	AC	679 ms; 34,964 KB
testcase_46	AC	591 ms; 34,416 KB
testcase_47	AC	561 ms; 35,188 KB
testcase_48	AC	586 ms; 35,480 KB
testcase_49	AC	613 ms; 35,704 KB
testcase_50	AC	644 ms; 34,496 KB
testcase_51	AC	428 ms; 35,856 KB
testcase_52	AC	324 ms; 35,000 KB
testcase_53	AC	281 ms; 34,532 KB
testcase_54	AC	295 ms; 34,924 KB
testcase_55	AC	267 ms; 35,280 KB
testcase_56	AC	504 ms; 19,872 KB
testcase_57	AC	391 ms; 14,904 KB
testcase_58	AC	374 ms; 20,280 KB
testcase_59	AC	374 ms; 12,800 KB
testcase_60	AC	531 ms; 26,284 KB
testcase_61	AC	666 ms; 34,540 KB
testcase_62	AC	374 ms; 19,964 KB
testcase_63	AC	648 ms; 21,572 KB
testcase_64	AC	801 ms; 34,816 KB
testcase_65	AC	464 ms; 22,300 KB
testcase_66	AC	2 ms; 6,940 KB
testcase_67	AC	2 ms; 6,944 KB
testcase_68	AC	2 ms; 6,940 KB
testcase_69	AC	2 ms; 6,940 KB
testcase_70	AC	2 ms; 6,944 KB

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <array>
#include <cmath>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
#define repr(i,n) for(int i=int(n)-1; i>=0; i--)
const i64 INF = 1001001001001001001;
const char* yn(bool x){ return x ? "Yes" : "No"; }
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
template<typename A> using nega_queue = std::priority_queue<A,std::vector<A>,std::greater<A>>;
template<class R> auto ComparingBy(R f){ return [g=std::move(f)](auto l, auto r) -> bool { return g(l) < g(r); }; }
#include <atcoder/modint>
using Modint = atcoder::static_modint<998244353>;
//#include "nachia/vec.hpp"
#include <cassert>

namespace nachia{

struct BbstListVoidPayload {
    static BbstListVoidPayload identity(){ return {}; }
    BbstListVoidPayload operator+(BbstListVoidPayload) const { return {}; }
};

struct BbstListVoidKey {
    bool operator<(BbstListVoidKey) const { return false; }
};

template<class Key, class Payload>
struct BbstList {
public:

struct FNode;
struct Node;

struct FNode {
    struct Node *p;
    unsigned int z;
    FNode(unsigned int _z) : p(nullptr), z(_z) {}
    struct Node *re(){ return (Node*)this; }
};

struct Iterator {
    using Item = typename Node::Item;
    FNode* p = nullptr;
    bool isEnd() const { return p->z == 0; }
    unsigned int index() const { return p->z ? p->re()->index() : p->p->z; }
    const Item& operator*() const { return p->re()->kv; }
    const Item* operator->() const { return &p->re()->kv; }
    Item getOr(Item ifEnd) const { return isEnd() ? ifEnd : (* *this); }
    bool operator==(Iterator r) const { return p == r.p; }
    bool operator!=(Iterator r) const { return p != r.p; }
    bool operator<(Iterator r) const { return index() < r.index(); }
    bool operator>(Iterator r) const { return index() > r.index(); }
    bool operator<=(Iterator r) const { return index() <= r.index(); }
    bool operator>=(Iterator r) const { return index() >= r.index(); }
    Iterator& operator++(){ p = p->re()->next(); return *this; }
    Iterator& operator--(){ p = (isEnd() ? p->p->back() : p->re()->prev()); return *this; }
    Iterator operator++(int) { auto res = *this; ++*this; return res; }
    Iterator operator--(int) { auto res = *this; --*this; return res; }
};

struct Node : public FNode {
    static inline Node* NIL;
    unsigned int h;
    struct Item { Key key; Payload val; } kv;
    Payload sum;
    Node *l = nullptr;
    Node *r = nullptr;
    Node()
        : FNode(0), h(0)
        , kv({Key(),Payload::identity()})
        , sum(Payload::identity()) {}
    Node(Key _key, Payload p)
        : FNode(1), h(1)
        , kv({std::move(_key),p})
        , sum(p) {}
    static Node* GetNil(){
        if(!NIL){
            NIL = new Node();
            NIL->l = NIL->r = NIL->p = NIL;
        }
        return NIL;
    }
    static Node* NewNode(Key key, Payload val){
        GetNil();
        Node *res = new Node(key, val);
        res->l = res->r = res->p = NIL;
        res->z = 1;
        return res;
    }
    static Node* Construct(std::vector<std::pair<Key, Payload>> val){
        for(size_t i=0; i+1<val.size(); i++) assert(!(val[i+1].first < val[i].first));
        auto s = [&](auto& s, int l, int r) -> Node* {
            if(l == r) return GetNil();
            int m = (l + r) / 2;
            auto buf = NewNode(std::move(val[m].first), std::move(val[m].second));
            buf->setChildren(s(s,l,m), s(s,m+1,r));
            return buf;
        };
        return s(s, 0, (int)val.size());
    }
    void aggregate(){
        sum = kv.val;
        h = 1; this->z = 1;
        sum = l->sum + sum; this->z += l->z; h = std::max(h, l->h + 1);
        sum = sum + r->sum; this->z += r->z; h = std::max(h, r->h + 1);
    }
    void setChildren(Node* lc, Node* rc){
        l = lc; if(lc != NIL) lc->p = this;
        r = rc; if(rc != NIL) rc->p = this;
        aggregate();
    }
    // if the 2 children have unbalanced height, fix them
    Node* rebalance(){
        auto c = this;
        auto cl = c->l;
        auto cr = c->r;
        if(cl->h + 1 < cr->h){
            auto crl = cr->l;
            auto crr = cr->r;
            if(crl->h <= crr->h){
                cr->p = c->p;
                c->setChildren(cl, crl);
                cr->setChildren(c, crr);
                return cr;
            } else{
                crl->p = c->p;
                c->setChildren(cl, crl->l);
                cr->setChildren(crl->r, crr);
                crl->setChildren(c, cr);
                return crl;
            }
        }
        else if(cl->h > cr->h + 1){
            auto cll = cl->l;
            auto clr = cl->r;
            if(clr->h <= cll->h){
                cl->p = c->p;
                c->setChildren(clr, cr);
                cl->setChildren(cll, c);
                return cl;
            } else{
                clr->p = c->p;
                c->setChildren(clr->r, cr);
                cl->setChildren(cll, clr->l);
                clr->setChildren(cl, c);
                return clr;
            }
        }
        aggregate();
        return this;
    }
    // call rebalance from this node to the root
    Node* rebalanceToRoot(){
        auto c = this;
        while(c->p != NIL){
            auto cp = c->p;
            (cp->l == c ? cp->l : cp->r) = c->rebalance();
            c = cp;
        }
        return c->rebalance();
    }
    Node* next(){
        auto c = this;
        if(c->r != NIL){
            c = c->r;
            while(c->l != NIL) c = c->l;
            return c;
        }
        while(c->p->r == c) c = c->p;
        return c->p;
    }
    Node* prev(){
        auto c = this;
        if(c->l != NIL){
            c = c->l;
            while(c->r != NIL) c = c->r;
            return c;
        }
        while(c->p->l == c) c = c->p;
        return c->p;
    }
    unsigned int index(){
        auto c = this;
        if(c == NIL) return ~0u;
        unsigned int res = c->l->z;
        while(c->p != NIL){
            auto cp = c->p;
            if(cp->r == c) res += cp->l->z + 1;
            c = cp;
        }
        return res;
    }
    // kth node under this, returns alt if not exist
    Node* kth(unsigned int idx, Node* alt){
        if(idx >= this->z) return alt;
        auto c = this;
        while(true){
            if(c->l->z > idx) c = c->l;
            else if(c->l->z == idx) break;
            else{ idx -= c->l->z + 1; c = c->r; }
        }
        return c;
    }
    // most left no-less-than k under this, and the next
    std::pair<Node*, Node*> lBound(Key k){
        Node *ql = NIL;
        Node *qr = NIL;
        auto c = this;
        while(c != NIL){
            if(c->kv.key < k){ ql = c; c = c->r; }
            else{ qr = c; c = c->l; }
        }
        return std::make_pair(ql, qr);
    }
    // most left grater-than k under this, and the next
    std::pair<Node*, Node*> uBound(Key k){
        Node *ql = NIL;
        Node *qr = NIL;
        auto c = this;
        while(c != NIL){
            if(k < c->kv.key){ qr = c; c = c->l; }
            else{ ql = c; c = c->r; }
        }
        return std::make_pair(ql, qr);
    }
    // update the payload and aggregate upto root
    void set(Payload val){
        kv.val = std::move(val);
        auto c = this;
        while(c != NIL){ c->aggregate(); c = c->p; }
    }
    static Node* rootOf(Node* p){
        while(p->p != NIL) p = p->p;
        return p;
    }
    static Payload rangeSumR(Node* l){
        assert(l != NIL);
        Payload res = l->kv.val + l->r->sum;
        auto lp = l->p;
        while(lp != NIL){
            if(lp->l == l) res = res + lp->kv.val + lp->r->sum;
            l = lp; lp = l->p;
        }
        return res;
    }
    static Payload rangeSum(Node* l, Node* r){
        assert(l != NIL);
        assert(r != NIL);
        assert(l != r);
        assert(rootOf(l) == rootOf(r));
        assert(l->index() <= r->index());
        r = r->prev();
        if(l == r) return l->kv.val;
        Payload lsum = l->kv.val;
        Payload rsum = r->kv.val;
        while(l != r){
            if(l->h < r->h){
                Node* lp = l->p;
                lsum = lsum + l->r->sum;
                while(lp->l != l){ l = lp; lp = l->p; }
                if(lp == r) return lsum + rsum;
                lsum = lsum + lp->kv.val;
                l = lp;
            } else {
                Node* rp = r->p;
                rsum = r->l->sum + rsum;
                while(rp->r != r){ r = rp; rp = r->p; }
                if(rp == l) return lsum + rsum;
                rsum = rp->kv.val + rsum;
                r = rp;
            }
        }
        return lsum + rsum;
    }
    template<class Pred>
    static Node* maxRight(Node* l, Pred& pred){
        Payload q = l->kv.val;
        if(!pred(q)) return l;
        while(true){
            Payload q2 = q + l->r->sum;
            if(!pred(q2)) break;
            l = l->p;
            if(l == NIL) return NIL;
            q = q2 + l->kv.val;
            if(!pred(q)) return l;
        }
        auto c = l->r;
        while(c != NIL){
            Payload q2 = q + c->l->sum;
            if(!pred(q2)){ c = c->l; continue; }
            q = q2 + c->kv.val;
            if(!pred(q)) return c;
            c = c->r;
        }
        return NIL;
    }
    void clear(){
        if(this == NIL) return;
        l->clear(); if(l != NIL) delete(l);
        r->clear(); if(r != NIL) delete(r);
    }
    Node* insert(Node* x){
        if(this == NIL) return x;
        auto q = lBound(x->kv.key);
        if(q.first != NIL && q.first->r == NIL){
            q.first->setChildren(q.first->l, x);
            return q.first->rebalanceToRoot();
        }
        q.second->setChildren(x, q.second->r);
        return q.second->rebalanceToRoot();
    }
    Node* erase(Node* ql, Node* qr){
        auto qlp = ql->p;
        Node* res = NIL;
        if(ql->r == NIL){
            auto qll = ql->l;
            if(qll != NIL) qll->p = qlp;
            if(qlp != NIL) (qlp->l == ql ? qlp->l : qlp->r) = qll;
            res = (qlp == NIL ? qll : qlp->rebalanceToRoot());
        } else {
            assert(qr != NIL);
            assert(qr->l == NIL);
            auto qrp = qr->p;
            auto qrr = qr->r;
            if(qlp != NIL) (qlp->l == ql ? qlp->l : qlp->r) = qr;
            qr->p = qlp;
            qr->l = ql->l;
            if(qr->l != NIL) qr->l->p = qr;
            if(ql->r == qr){
                qr->aggregate();
                res = qr->rebalanceToRoot();
            } else {
                (qrp->l == qr ? qrp->l : qrp->r) = qrr;
                if(qrr != NIL) qrr->p = qrp;
                qr->r = ql->r;
                qr->r->p = qr;
                qr->aggregate();
                res = qrp->rebalanceToRoot();
            }
        }
        ql->l = ql->r = ql->p = NIL;
        ql->aggregate();
        return res;
    }
    Node* back(){
        auto c = this;
        while(c->r != NIL) c = c->r;
        return c;
    }
};

    BbstList() : rt(0) { rt.p = Node::GetNil(); }
    BbstList(std::vector<std::pair<Key, Payload>> init) : rt(0) { rt.p = Node::Construct(std::move(init)); }
    Iterator end(){ return {&rt}; }
    Iterator begin(){
        FNode *p = rt.p->z ? rt.p->kth(0,nullptr) : &rt;
        return {p};
    }
    void clear(){
        if(rt.p != Node::GetNil()){
            rt.p->clear();
            delete(rt.p);
            rt.p = Node::NIL;
        }
    }
    ~BbstList(){ clear(); }
    int size() const { return rt.p->z; }
    bool empty() const { return rt.p == Node::NIL; }
    Payload sum(Iterator l, Iterator r, Payload ifnull){
        if(l == r) return ifnull;
        if(r == end()) return Node::rangeSumR(l.p->re());
        return Node::rangeSum(l.p->re(), r.p->re());
    }
    Iterator kth(unsigned int idx){
        auto p = root()->kth(idx, nullptr);
        return p ? Iterator{p} : end();
    }
    Iterator lBound(Key key){
        auto p = root()->lBound(std::move(key)).second;
        return p == Node::NIL ? end() : Iterator{p};
    }
    Iterator uBound(Key key){
        auto p = root()->uBound(std::move(key)).second;
        return p == Node::NIL ? end() : Iterator{p};
    }
    Iterator lBoundL(Key key){
        auto p = root()->lBound(std::move(key)).first;
        return p == Node::NIL ? end() : Iterator{p};
    }
    Iterator uBoundL(Key key){
        auto p = root()->uBound(std::move(key)).first;
        return p == Node::NIL ? end() : Iterator{p};
    }
    Iterator find(Key key){
        auto p = lBound(key);
        return (p.isEnd() || key < p->key) ? end() : p;
    }
    Iterator insert(Key k, Payload v){
        auto x = Node::NewNode(std::move(k), std::move(v));
        rt.p = root()->insert(x);
        return Iterator{ x };
    }
    Iterator erase(Iterator i){
        if(i == end()) return i;
        auto nx = i; ++nx;
        auto nxv = nx == end() ? Node::NIL : nx.p->re();
        rt.p = root()->erase(i.p->re(), nxv);
        delete(i.p->re());
        return nx;
    }
    Iterator changeKey(Iterator i, Key k){
        if(i == end()) return i;
        auto nx = i; ++nx;
        auto ptr = i.p->re();
        auto nxv = nx == end() ? Node::NIL : nx.p->re();
        rt.p = root()->erase(i.p->re(), nxv);
        ptr->kv.key = std::move(k);
        rt.p = root()->insert(i.p->re());
        return i;
    }
    void set(Iterator pos, Payload val){ pos.p->re()->set(val); }
    void output(){ root()->output(); }
    
private:
    FNode rt;
    Node* root(){ return rt.p->re(); }
};

} // namespace nachia
using namespace std;

void testcase(){
    int N, Q; cin >> N >> Q;
    vector<i64> A(N); rep(i,N) cin >> A[i];
    using Ds = nachia::BbstList<i64, nachia::BbstListVoidPayload>;
    vector<pair<Ds::Iterator,pair<int,i64>>> F;
    auto s = Ds();
    vector<Ds::Iterator> pt;
    rep(i,N) F.push_back({ s.insert(i, {}), {i,A[i]} });
    auto acc = [&](i64 k) -> auto {
        return s.kth(k);
    };
    rep(qi,Q){
        int t; cin >> t;
        if(t == 3){
            int k; cin >> k; k--;
            if(A[k] == -1){
                cout << s.kth(k)->key << '\n';
            } else {
                cout << A[k] << '\n';
            }
        }
        else if(t == 1){
            int k; cin >> k; k--;
            i64 x; cin >> x;
            A[k] = x;
            F.push_back({ s.kth(k), {k,x} });
        }
        else if(t == 2){
            for(auto [k,x] : F){
                s.changeKey(k, x.second);
                A[x.first] = -1;
            }
            F.clear();
        }
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}