#228622 (C++14) No.318 学学学学学

• 問題: No.318 学学学学学
• ユーザー: ふーらくたる
• 提出日時: 2018-01-09 00:01:58
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 148 ms / 2,000 ms
• コード長: 4,394 bytes
• コンパイル時間: 956 ms
• コンパイル使用メモリ: 83,940 KB
• 実行使用メモリ: 14,208 KB
• 最終ジャッジ日時: 2024-06-22 18:30:13
• 合計ジャッジ時間: 3,714 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 26

ソースコード

#include <iostream>
#include <vector>
#include <limits>
#include <map>
using namespace std;

struct RUQ_SET {
    using T = int;
    static inline constexpr T identity() { return std::numeric_limits<int>::max(); }
    // static inline T op(const T& a, const T& b) { return a + b; }
};

template <class Object>
struct RUQ_OP {
    using T = typename Object::T;
    using M = T;
    static inline constexpr M identity() { return -1; }
    static inline M op(const M& a, const M& b) { return (b == identity()) ? a : b; }
    // mpをaに適用する
    static inline T apply(const M& mp, const int a, int w) { return (mp == identity()) ? a : T(mp); }
};

// 区間更新一点取得
template <class Object, class Operator>
class LazyPropagationSegmentTree {
    const int N;
    const int h;
    using T = typename Object::T;
    using M = typename Operator::M;
    std::vector<T> t;
    std::vector<M> lazy;

    inline int lowest_pow_of_2(int n) {
        int res = 1;
        while (res < n) res <<= 1;
        return res;
    }

    // log2_X <= nを満たす最大のXを計算
    inline int log2(int n) {
        int res = 0;
        while (n >> (res + 1)) res++;
        return res;
    }

    inline void prop_to(int i) {
        t[i] = Object::op(t[2 * i], t[2 * i + 1]);
    }

    inline void eval(int i, int w) {
        if (i < N and lazy[i] != Operator::identity()) {
            t[i] = Operator::apply(lazy[i], t[i], w);

            if (2 * i < N) {
                // 伝搬
                lazy[2 * i] = Operator::op(lazy[2 * i], lazy[i]);
                lazy[2 * i + 1] = Operator::op(lazy[2 * i + 1], lazy[i]);
            } else if (i < N) {
                t[2 * i] = Operator::apply(lazy[i], t[2 * i], w / 2);
                t[2 * i + 1] = Operator::apply(lazy[i], t[2 * i + 1], w / 2);
            }
            lazy[i] = Operator::identity();
        }
    }

    public:

    LazyPropagationSegmentTree(int n)
        : N(lowest_pow_of_2(n)), h(log2(N) + 1),
          t(2 * N, Object::identity()), lazy(N, Operator::identity()) { }

    template <class InputIt>
    LazyPropagationSegmentTree(InputIt first, InputIt last)
        : N(lowest_pow_of_2(std::distance(first, last))),
          h(log2(N) + 1), 
          t(2 * N, Object::identity()),
          lazy(N, Operator::identity()) {
        std::copy(first, last, t + N);
        for (int i = N - 1; i > 0; i--) prop_to(i);
    }

    inline void update(int l, int r, M mp) {
        update(l, r, mp, 1, 0, N);
    }

    inline void update(int l, int r, M mp, int id, int nodel, int noder) {
        // 範囲外
        eval(id, noder - nodel);   // 演算の順序を守るためさきに伝播させる
        if (noder <= l or r <= nodel) return;

        if (id >= N) {  // 葉
            t[id] = Operator::apply(mp, t[id], 1);
            return;
        }

        if (l <= nodel and noder <= r) {
            lazy[id] = Operator::op(lazy[id], mp);
            eval(id, noder - nodel);
        } else {
            update(l, r, mp, 2 * id, nodel, (nodel + noder) / 2);
            update(l, r, mp, 2 * id + 1, (nodel + noder) / 2, noder);
            // t[id] = Object::op(t[2 * id], t[2 * id + 1]);
        }
    }

    T get(int i) {
        i += N;
        for (int j = (h - 1); j > 0; j--) eval(i >> j, 1 << j);
        return t[i];
    }

    /*
    T query(int l, int r) {
        return query(l, r, 1, 0, N);
    }
    T query(int l, int r, int id, int nodel, int noder) {
        // 範囲外
        eval(id, noder - nodel);
        if (noder <= l or r <= nodel) return Object::identity();
        // 完全に含まれる
        if (l <= nodel and noder <= r) return t[id];
        T resl = query(l, r, 2 * id, nodel, (nodel + noder) / 2);
        T resr = query(l, r, 2 * id + 1, (nodel + noder) / 2, noder);
        return Object::op(resl, resr);
    }
    */
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    map<int, int> left, right;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;

        if (left.count(a) == 0) left[a] = i;
        right[a] = i;
    }

    LazyPropagationSegmentTree<RUQ_SET, RUQ_OP<RUQ_SET>> segtree(N);
    for (auto p : left) segtree.update(p.second, right[p.first] + 1, p.first);
    for (int i = 0; i < N; i++) {
        cout << segtree.get(i) << " ";
    }
    cout << endl;

    return 0;
}