#708563 (C++17) No.1705 Mode of long array

• 問題: No.1705 Mode of long array
• ユーザー: みしあ
• 提出日時: 2021-10-21 21:46:09
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 248 ms / 3,000 ms
• コード長: 5,758 bytes
• コンパイル時間: 4,550 ms
• コンパイル使用メモリ: 268,808 KB
• 実行使用メモリ: 9,516 KB
• 最終ジャッジ日時: 2023-10-21 17:04:57
• 合計ジャッジ時間: 14,308 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	4 ms; 4,348 KB
testcase_04	AC	3 ms; 4,348 KB
testcase_05	AC	4 ms; 4,348 KB
testcase_06	AC	10 ms; 4,348 KB
testcase_07	AC	13 ms; 4,348 KB
testcase_08	AC	13 ms; 4,348 KB
testcase_09	AC	11 ms; 4,348 KB
testcase_10	AC	10 ms; 4,348 KB
testcase_11	AC	11 ms; 4,348 KB
testcase_12	AC	11 ms; 4,348 KB
testcase_13	AC	169 ms; 9,516 KB
testcase_14	AC	125 ms; 6,416 KB
testcase_15	AC	129 ms; 4,348 KB
testcase_16	AC	153 ms; 4,348 KB
testcase_17	AC	112 ms; 4,348 KB
testcase_18	AC	91 ms; 4,348 KB
testcase_19	AC	173 ms; 4,832 KB
testcase_20	AC	106 ms; 4,832 KB
testcase_21	AC	130 ms; 9,516 KB
testcase_22	AC	201 ms; 9,516 KB
testcase_23	AC	104 ms; 4,348 KB
testcase_24	AC	103 ms; 4,348 KB
testcase_25	AC	103 ms; 4,348 KB
testcase_26	AC	103 ms; 4,348 KB
testcase_27	AC	104 ms; 4,348 KB
testcase_28	AC	102 ms; 4,348 KB
testcase_29	AC	105 ms; 4,348 KB
testcase_30	AC	104 ms; 4,348 KB
testcase_31	AC	103 ms; 4,348 KB
testcase_32	AC	102 ms; 4,348 KB
testcase_33	AC	202 ms; 9,516 KB
testcase_34	AC	195 ms; 9,516 KB
testcase_35	AC	205 ms; 9,516 KB
testcase_36	AC	196 ms; 9,516 KB
testcase_37	AC	200 ms; 9,516 KB
testcase_38	AC	198 ms; 9,516 KB
testcase_39	AC	203 ms; 9,516 KB
testcase_40	AC	197 ms; 9,516 KB
testcase_41	AC	199 ms; 9,516 KB
testcase_42	AC	200 ms; 9,516 KB
testcase_43	AC	248 ms; 9,516 KB
testcase_44	AC	245 ms; 9,516 KB
testcase_45	AC	244 ms; 9,516 KB
testcase_46	AC	244 ms; 9,516 KB
testcase_47	AC	247 ms; 9,516 KB
testcase_48	AC	246 ms; 9,516 KB
testcase_49	AC	212 ms; 9,516 KB
testcase_50	AC	211 ms; 9,516 KB
testcase_51	AC	209 ms; 9,516 KB
testcase_52	AC	214 ms; 9,516 KB
testcase_53	AC	216 ms; 9,516 KB

ソースコード

#pragma region Macros
#include <bits/stdc++.h>
#if defined(LOCAL) || defined(ONLINE_JUDGE) || defined(_DEBUG)
#include <atcoder/all>
#endif
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>using vec = vector<T>;
template<class T, class U>using umap = unordered_map<T, U>;
template<class T>using uset = unordered_set<T>;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vl = vec<ll>;
#define fi first
#define se second
#define el endl
constexpr ll INF = numeric_limits<ll>::max()/2-1;
#pragma endregion

#pragma region IOMacros
template<class T>
istream &operator>>(istream &stream, vec<T>& o){REP(i, o.size())stream >> o[i];return stream;}
template<class T>
ostream &operator<<(ostream &stream, vec<T>& objs){REP(i, objs.size())stream << objs[i] << " ";stream << el;return stream;}

#define I(T, ...) ;T __VA_ARGS__;__i(__VA_ARGS__);
void __i() {}
template<class T, class... Ts> void __i(T&& o, Ts&&... args){cin >> o;__i(forward<Ts>(args)...);}

void O() {cout << el;}
template<class T, class... Ts> void O(T&& o, Ts&&... args){cerr << o << " ";O(forward<Ts>(args)...);}
#pragma endregion

void Main();

int main(){
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

// 遅延セグメント木
#pragma region LazySegmentTree
// https://ei1333.github.io/algorithm/segment-tree.html
// [l, r)
namespace LSTOpt{
    using Monoid = P;
    using OpMonoid = ll;
    // Command基底クラスの宣言
    struct CmdM{
        virtual Monoid M() = 0;
        virtual Monoid op(Monoid a, Monoid b) = 0;
        virtual OpMonoid p(OpMonoid a, size_t n) = 0;
    };
    struct CmdOp{
        virtual OpMonoid ID() = 0;
        virtual Monoid mapping(Monoid a, OpMonoid b) = 0;
        virtual OpMonoid composition(OpMonoid a, OpMonoid b) = 0;
    };
}
template< typename Monoid = LSTOpt::Monoid, typename OperatorMonoid = LSTOpt::OpMonoid >
struct LST {
    int sz;
    vector< Monoid > data;
    vector< OperatorMonoid > lazy;
    LSTOpt::CmdM* m;
    LSTOpt::CmdOp* op;
    LST(int n, LSTOpt::CmdM* cmdm, LSTOpt::CmdOp* cmdop)
        //: f(cmdm.op), g(cmdop.mapping), h(cmdop.composition), p(cmdm.p), M1(cmdm.M()), OM0(cmdop.ID())
        {
            this->m = cmdm;
            this->op = cmdop;
            sz = 1;
            while(sz < n) sz <<= 1;
            data.assign(2 * sz, m->M());
            lazy.assign(2 * sz, op->ID());
        }

    void set(int k, const Monoid &x) {
        data[k + sz] = x;
    }
    void build(){
        for(int k = sz - 1; k > 0; k--) {
            data[k] = m->op(data[2 * k + 0], data[2 * k + 1]);
        }
    }
    void propagate(int k, int len) {
        if(lazy[k] != op->ID()) {
            if(k < sz) {
                lazy[2 * k + 0] = op->composition(lazy[2 * k + 0], lazy[k]);
                lazy[2 * k + 1] = op->composition(lazy[2 * k + 1], lazy[k]);
            }
            data[k] = op->mapping(data[k], m->p(lazy[k], len));
            lazy[k] = op->ID();
        }
    }
    Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r) {
        propagate(k, r - l);
        if(r <= a || b <= l) {
            return data[k];
        }else if(a <= l && r <= b) {
            lazy[k] = op->composition(lazy[k], x);
            propagate(k, r - l);
            return data[k];
        }else{
            return data[k] = m->op(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                                update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
        }
    }
    Monoid update(int a, int b, const OperatorMonoid &x) {
        return update(a, b, x, 1, 0, sz);
    }
    Monoid query(int a, int b, int k, int l, int r){
        propagate(k, r - l);
        if(r <= a || b <= l) {
            return m->M();
        }else if(a <= l && r <= b) {
            return data[k];
        }else{
            return m->op(query(a, b, 2 * k + 0, l, (l + r) >> 1),
                    query(a, b, 2 * k + 1, (l + r) >> 1, r));
        }
    }
    Monoid query(int a, int b) {
        return query(a, b, 1, 0, sz);
    }
    Monoid operator[](const int &k) {
        return query(k, k + 1);
    }
};
namespace LSTOpt{
    struct secadd : CmdOp{
        // 単位元
        OpMonoid ID(){ return 0; }
        // 要素と作用素のマージ
        Monoid mapping(Monoid a, OpMonoid b) { return {a.fi + b, a.se}; };
        // 作用素と作用素のマージ
        OpMonoid composition(OpMonoid a, OpMonoid b) { return a + b; };
    } ;
    // max
    struct secmax : CmdM{
        // 単位元
        Monoid M(){ return {-INF, -INF}; }
        // 演算
        Monoid op(Monoid a, Monoid b){ return std::max(a, b); }
        // 作用素マージの前にかませる関数
        OpMonoid p(OpMonoid a, size_t n){ return a; }
    };
};
#pragma endregion

void Main(){
    I(ll, N, M);
    LST lst(M, new LSTOpt::secmax(), new LSTOpt::secadd());
    REP(i, M){
        I(ll, a);
        lst.set(i, {a, i+1});
    }
    lst.build();
    I(ll, Q);
    REP(i, Q){
        I(ll, T, X, Y);
        switch (T)
        {
        case 1:
            lst.update(X-1, X, Y);break;
        case 2:
            lst.update(X-1, X, -Y);break;
        case 3:
            cout << lst.query(0, M).se << el;break;
        }
    }
}