結果

問題 No.1705 Mode of long array
コンテスト
ユーザー みしあ
提出日時 2021-10-21 21:46:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 289 ms / 3,000 ms
コード長 5,758 bytes
コンパイル時間 5,029 ms
コンパイル使用メモリ 255,464 KB
最終ジャッジ日時 2025-01-25 02:36:40
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
        }
    }
}
0