結果

問題 No.875 Range Mindex Query
ユーザー WarToksWarToks
提出日時 2020-09-28 15:14:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 18,433 bytes
コンパイル時間 650 ms
コンパイル使用メモリ 80,052 KB
最終ジャッジ日時 2024-11-14 23:50:49
合計ジャッジ時間 1,209 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:291:64: error: 'numeric_limits' is not a member of 'std'
  291 |     inline static constexpr value_type identity_element = std::numeric_limits<int>::max();  // データの単位元
      |                                                                ^~~~~~~~~~~~~~
main.cpp:291:79: error: expected primary-expression before 'int'
  291 |     inline static constexpr value_type identity_element = std::numeric_limits<int>::max();  // データの単位元
      |                                                                               ^~~
main.cpp:291:78: error: expected ';' at end of member declaration
  291 |     inline static constexpr value_type identity_element = std::numeric_limits<int>::max();  // データの単位元
      |                                                                              ^
      |                                                                               ;
main.cpp:291:82: error: expected unqualified-id before '>' token
  291 |     inline static constexpr value_type identity_element = std::numeric_limits<int>::max();  // データの単位元
      |                                                                                  ^

ソースコード

diff #

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <array>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>

template <class InputIterator>
std::ostream& range_output(std::ostream& os_arg, InputIterator first_arg, InputIterator last_arg){ if(first_arg != last_arg){ do{ os_arg << *(first_arg++); if(first_arg == last_arg) break; os_arg << ' '; } while(true); }  return os_arg; }
template <class Tp> std::ostream& operator << (std::ostream& os_arg, const std::vector<Tp>& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); }
template <class Tp, std::size_t Size> std::ostream& operator << (std::ostream& os_arg, const std::array<Tp, Size>& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); }
template <class S, class T> std::ostream& operator << (std::ostream& os_arg, const std::pair<S, T>& pair_arg){ return os_arg << '(' << pair_arg.first << ", " << pair_arg.second << ')'; }

#ifndef ONLINE_JUDGE
    template <typename Head> void dump_out(Head head_arg){ std::cerr << head_arg << '\n'; }
    template <typename Head, typename... Tail>
    void dump_out(Head head_arg, Tail... tail_args){ std::cerr << head_arg << ", "; dump_out(tail_args...); }
    #define dump(...) do { std::cerr << "[in line " << __LINE__ << "] " << #__VA_ARGS__ << " : "; dump_out(__VA_ARGS__); } while(false)
#else
    #define dump(...) (void(0))
#endif

// @ 遅延伝搬セグメント木 (データ構造)
// * 区間更新, 区間取得 が O(logN) で達成可能である
//   下のマクロは 区間の「位置」 [L, R) の情報を用いるかのマクロ
//        if : true  -> 用いる   : merge に 区間 [L, R) (0-indexed) の情報を用いる
//        if : false -> 用いない : merge に 区間幅 N を用いることができる
#define USE_RANGE_INFO_FOR_LAZY_SEGTREE false

// ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
//    struct monoid_lazy_segment_tree{
//        using value_type = ;          // データの型
//        using lazy_type = ;           // 遅延評価作用素の型
//        inline static constexpr value_type identity_element = 0;  // データの単位元
//        // データ型の演算 (クエリの畳み込み和の演算) : 他ライブラリでは f などで書かれている
//        static value_type operation(const value_type& x, const value_type& y){
//            return ;
//        }
//    #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
//        // 遅延評価を実際に行う演算 : (更新(評価)されるデータ型の値, 遅延作用素, その区間 [L, R)) → 新しく評価するデータの値
//        // ※※※ 配列参照外に注意する必要はない ※※※
//        static value_type merge(const value_type& x, const lazy_type& y, const int L, const int R){
//            return ;
//        }
//    #else 
//        // 遅延評価を実際に行う演算 : (更新(評価)されるデータ型の値, 遅延作用素, その区間幅 N → 新しく評価するデータの値
//        static value_type merge(const value_type& x, const lazy_type& y, const int N){
//            return ;
//        }
//    #endif
//        // 遅延作用素の伝搬 (古い作用素, 新しい作用素) → (作用素)
//        static lazy_type propagate(const lazy_type& x, const lazy_type& y){
//            return ;
//        }
//    };
// ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
template <class monoid_lazy_segment_tree> class LazySegmentTree{
private:
    using element_t   = typename monoid_lazy_segment_tree::value_type;
    using lazy_t      = typename monoid_lazy_segment_tree::lazy_type;
    using lazy_opt_t  = std::optional<lazy_t>;
    const int arr_len;             //  扱う配列の長さ n
    const int height;              //  セグメント木の高さ : 要素数 2^k の k
    const int length;              //  セグメント木の要素数 : 2^k (dataの数は 2 * 2^k)
    std::vector<element_t> data;   //  要素の部分
    std::vector<lazy_opt_t> lazy;  //  遅延評価部分

    // セグメント木に必要な高さを計算する補助関数
    static int make_height(const int n){
        int res = 0; for(int len = 1; len < n; ++res, len <<= 1);
        return res;
    }

    // 葉である頂点 x から 根に向かってボトムアップに 要素本体 (data) の値を lazy を元に更新していく関数
    inline void calculateData(int x){
    #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
        for(int shift = 0, len = 1; x /= 2; ++shift, len *= 2){
            const int c1 = 2 * x, c2 = c1 + 1;
            const int cl1 = (c1 ^ (1 << (height - shift))) << shift, cl2 = cl1 + len;
            // 左端が arr_len より大きい区間は更新されない(lazyはstd::nullopt) → 右端のみを arr_len に丸める
            data[x] = monoid_lazy_segment_tree::operation(
                lazy[c1] ? monoid_lazy_segment_tree::merge(data[c1], *lazy[c1], cl1, std::min(cl2, arr_len)) : data[c1],
                lazy[c2] ? monoid_lazy_segment_tree::merge(data[c2], *lazy[c2], cl2, std::min(cl2 + len, arr_len)) : data[c2]
            );
        }
    #else
        for(int len = 1; x /= 2; len *= 2){
            const int c1 = 2 * x, c2 = c1 + 1;
            data[x] = monoid_lazy_segment_tree::operation(
                lazy[c1] ? monoid_lazy_segment_tree::merge(data[c1], *lazy[c1], len) : data[c1],
                lazy[c2] ? monoid_lazy_segment_tree::merge(data[c2], *lazy[c2], len) : data[c2]
            );
        }
    #endif
    }
    // 葉である頂点 x に向かって根からトップダウンに遅延評価部(lazy)を伝搬させていく関数
    inline void propagate(int x){
        for(int shift = height, len = 1 << shift; shift ; --shift, len /= 2){
            const int idx = x >> shift;
            if(lazy[idx]){
                const int idx1 = 2 * idx;
                lazy[idx1] = lazy[idx1] ? lazy_opt_t(monoid_lazy_segment_tree::propagate(*lazy[idx1], *lazy[idx])) : lazy[idx];
                const int idx2 = 2 * idx + 1;
                lazy[idx2] = lazy[idx2] ? lazy_opt_t(monoid_lazy_segment_tree::propagate(*lazy[idx2], *lazy[idx])) : lazy[idx];
    #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
                const int ldx = (idx ^ (1 << (height - shift))) << shift;
                // 左端が arr_len より大きい区間は更新されない(lazyはstd::nullopt) → 右端のみを arr_len に丸める
                data[idx] = monoid_lazy_segment_tree::merge(data[idx], *lazy[idx], ldx, std::min(ldx + len, arr_len));
    #else
                data[idx] = monoid_lazy_segment_tree::merge(data[idx], *lazy[idx], len);
    #endif
                lazy[idx] = std::nullopt;
            }
        }
    #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
        if(lazy[x]){ data[x] = monoid_lazy_segment_tree::merge(data[x], *lazy[x], x - length, x - length + 1); lazy[x] = std::nullopt; }
    #else
        if(lazy[x]){ data[x] = monoid_lazy_segment_tree::merge(data[x], *lazy[x], 1); lazy[x] = std::nullopt; }
    #endif
    }

public:
    // コンストラクタ
    LazySegmentTree(const int len): arr_len(len), height(make_height(arr_len)), length(1 << height){
        data.assign(2 * length, monoid_lazy_segment_tree::identity_element);
        lazy.assign(2 * length, std::nullopt);
    }
    LazySegmentTree(const int len, const element_t& init_value): arr_len(len), height(make_height(arr_len)), length(1 << height){
        data.resize(2 * length); 
        std::fill(data.begin() + length, data.begin() + length + len, init_value);
        std::fill(data.begin() + length + len, data.end(), monoid_lazy_segment_tree::identity_element);
        for(int idx = length - 1; idx > 0; --idx) data[idx] = monoid_lazy_segment_tree::operation(data[2 * idx], data[2 * idx + 1]);
        lazy.assign(2 * length, std::nullopt);
    }
    LazySegmentTree(const std::vector<element_t>& A): arr_len(A.size()), height(make_height(arr_len)), length(1 << height){
        lazy.assign(2 * length, std::nullopt);
        data.resize(2 * length); std::copy(A.begin(), A.end(), data.begin() + length);
        std::fill(data.begin() + length + A.size(), data.end(), monoid_lazy_segment_tree::identity_element);
        for(int idx = length - 1; idx > 0; --idx) data[idx] = monoid_lazy_segment_tree::operation(data[2 * idx], data[2 * idx + 1]);
    }
    template <class InputIterator>
    LazySegmentTree(InputIterator first, InputIterator last):arr_len(last - first), height(make_height(arr_len)), length(1 << height){
        lazy.assign(2 * length, std::nullopt);
        data.resize(2 * length); std::copy(first, last, data.begin() + length);
        std::fill(data.begin() + length + (last - first), data.end(), monoid_lazy_segment_tree::identity_element);
        for(int idx = length - 1; idx; --idx) data[idx] = monoid_lazy_segment_tree::operation(data[2 * idx], data[2 * idx + 1]);
    }

    // @ 半開区間 [l, r) (0-indexed) に作用素 val を作用させる関数 : 計算量 O(logN)
    inline void update_range(int l, int r, const lazy_t& val){
        assert(0 <= l and l <= r and r <= arr_len);
        if(l == r) return ;
        propagate(l += length); propagate(r += length - 1);
        for(int li = l, ri = r + 1; li < ri; li >>= 1, ri >>= 1){
            if(li & 1){ lazy[li] = lazy[li] ? monoid_lazy_segment_tree::propagate(*lazy[li], val) : val; li++; }
            if(ri & 1){ --ri; lazy[ri] = lazy[ri] ? monoid_lazy_segment_tree::propagate(*lazy[ri], val) : val; }
        }
        calculateData(l); calculateData(r);
    }
    // @ 1点 index (0-indexed) に作用素 val を作用させる関数
    inline void update_at(int index, const lazy_t& val){
        assert(0 <= index and index < arr_len);
        propagate(index += length);
    #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
        data[index] = monoid_lazy_segment_tree::merge(data[index], val, index - length, index - length + 1);
    #else
        data[index] = monoid_lazy_segment_tree::merge(data[index], val, 1);
    #endif
        calculateData(index);
    }
    // @ 1点 index (0-indexed) に直接, 値 val を「代入」する関数
    inline void assign_at(int index, const element_t& val){
        assert(0 <= index and index < arr_len);
        propagate(index += length);
        data[index] = val;
        calculateData(index);
    }

    // @ 半開区間 [l, r) (0-indexed) 上の畳み込み和 al * al+1 * ... * ar-1 を求める関数
    inline element_t fold_range(int l, int r){
        assert(0 <= l and l <= r and r <= arr_len);
        if(l == r) return monoid_lazy_segment_tree::identity_element;
        propagate(l += length); propagate((r += length) - 1);
        element_t vl = monoid_lazy_segment_tree::identity_element, vr = monoid_lazy_segment_tree::identity_element;
    #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
        for(int shift = 0, len = 1; l < r ; l /= 2, r /= 2, len *= 2, ++shift){
            if(l & 1){
                if(lazy[l]){
                    const int ll = (l ^ (1 << (height - shift))) << shift;
                    vl = monoid_lazy_segment_tree::operation(vl, monoid_lazy_segment_tree::merge(data[l], *lazy[l], ll, ll + len));
                }
                else vl = monoid_lazy_segment_tree::operation(vl, data[l]);
                l++;
            }
            if(r & 1){
                --r; 
                if(lazy[r]){
                    const int rl = (r ^ (1 << (height - shift))) << shift;
                    vr = monoid_lazy_segment_tree::operation(monoid_lazy_segment_tree::merge(data[r], *lazy[r], rl, rl + len), vr);
                }
                else vr = monoid_lazy_segment_tree::operation(data[r], vr);
            }
        }
    #else
        for(int len = 1; l < r; l /= 2, r /= 2, len *= 2){
            if(l & 1){
                vl = monoid_lazy_segment_tree::operation( vl, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], len) : data[l] ); l++;
            }
            if(r & 1){
                --r; vr = monoid_lazy_segment_tree::operation(lazy[r] ? monoid_lazy_segment_tree::merge(data[r], *lazy[r], len) : data[r], vr);
            }
        }
    #endif
        return monoid_lazy_segment_tree::operation(vl, vr);
    }
    // @ 全区間の畳み込み和を求める関数 : O(1)
    inline element_t fold_all(void) const { return data[1]; }

    // @ 1点 index (0-indexed) の値を得る関数 : O(logN)
    inline element_t fold_at(int index){ propagate(index += length); return data[index]; }

    // @ 1点 index (0-indexed) の値を得る関数 : O(logN)
    inline const element_t& operator [](int index){ propagate(index += length); return data[index]; }

    // @ セグ木上の二分探索(右側) : 初めて comp(∑_[l, r) ai) が初めて true となる右端 r を返す (存在しない場合, -1 を返す)
    //  仮定 ; 比較関数に対して false, false, ..., true, ... という単調性がある
    template <class Compare_t> int right_search(int l, Compare_t comp){
        assert(0 <= l and l <= arr_len);
        if(comp(monoid_lazy_segment_tree::identity_element)) return l;
        if(l == arr_len) return -1;
        propagate(l += length);
        element_t l_sum = monoid_lazy_segment_tree::identity_element;
        do {
            int shift = 0, len = 1;
            for(; l % 2 == 0; l /= 2, ++shift, len *= 2);
        #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
            const int ll = (l ^ (1 << (height - shift))) << shift; if(arr_len <= ll) return -1;
            const element_t tmp_val = monoid_lazy_segment_tree::operation(
                l_sum, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], ll, std::min(arr_len, ll + len)) : data[l]
            );
        #else
            const element_t tmp_val = monoid_lazy_segment_tree::operation( l_sum, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], len) : data[l] );
        #endif
            if(comp(tmp_val)){
                while(l < length){
                    if(lazy[l]){
                        const int idx1 = 2 * l;
                        lazy[idx1] = lazy[idx1] ? lazy_opt_t(monoid_lazy_segment_tree::propagate(*lazy[idx1], *lazy[l])) : lazy[l];
                        const int idx2 = 2 * l + 1;
                        lazy[idx2] = lazy[idx2] ? lazy_opt_t(monoid_lazy_segment_tree::propagate(*lazy[idx2], *lazy[l])) : lazy[l];
        #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
                        const int lll = (l ^ (1 << (height - shift))) << shift;
                        if(arr_len <= lll) return -1;
                        // 左端が arr_len より大きい区間は更新されない(lazyはstd::nullopt) → 右端のみを arr_len に丸める
                        data[l] = monoid_lazy_segment_tree::merge(data[l], *lazy[l], lll, std::min(lll + len, arr_len));
        #else
                        data[l] = monoid_lazy_segment_tree::merge(data[l], *lazy[l], len);
        #endif
                        lazy[l] = std::nullopt;
                    }
                    l *= 2; len *= 2; --shift;
        #if USE_RANGE_INFO_FOR_LAZY_SEGTREE
                    const int lll = (l ^ (1 << (height - shift))) << shift; if(arr_len <= lll) return -1;
                    const element_t tmp_val2 = monoid_lazy_segment_tree::operation(
                        l_sum, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], lll, std::min(arr_len, lll + len)) : data[l]
                    );
        #else
                    const element_t tmp_val2 = monoid_lazy_segment_tree::operation( l_sum, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], len) : data[l] );
        #endif
                    if(not comp(tmp_val2)){ l_sum = tmp_val2; ++l; }
                }
                return l - length + 1;
            }
            l_sum = tmp_val;
            l++;
        } while ((l & -l) != l);
        return -1;
    }

    template <bool (*comp)(const element_t&)> int right_search(int l){
        return right_search(l, [](const element_t& x){ return comp(x); });
    }
};

// ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
struct monoid_lazy_segment_tree{
    using value_type = long long int;          // データの型
    using lazy_type = int;           // 遅延評価作用素の型
    inline static constexpr value_type identity_element = std::numeric_limits<int>::max();  // データの単位元
    // データ型の演算 (クエリの畳み込み和の演算) : 他ライブラリでは f などで書かれている
    static value_type operation(const value_type& x, const value_type& y){
        return (x < y) ? x : y;
    }
#if USE_RANGE_INFO_FOR_LAZY_SEGTREE
    // 遅延評価を実際に行う演算 : (更新(評価)されるデータ型の値, 遅延作用素, その区間 [L, R)) → 新しく評価するデータの値
    // ※※※ 配列参照外に注意する必要はない ※※※
    static value_type merge(const value_type& x, const lazy_type& y, const int L, const int R){
        return y;
    }
#else 
    // 遅延評価を実際に行う演算 : (更新(評価)されるデータ型の値, 遅延作用素, その区間幅 N → 新しく評価するデータの値
    static value_type merge(const value_type& x, const lazy_type& y, const int N){
        return y;
    }
#endif
    // 遅延作用素の伝搬 (古い作用素, 新しい作用素) → (作用素)
    static lazy_type propagate(const lazy_type& x, const lazy_type& y){
        return y;
    }
};


int main(void){
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); 
    std::cout << std::fixed << std::setprecision(16);
    
    int n, q; std::cin >> n >> q;
    std::vector<int> A(n); for(auto& itr : A){ std::cin >> itr; --itr; }
    LazySegmentTree<monoid_lazy_segment_tree> LST(A.cbegin(), A.cend());
    std::vector<int> Arg(n); for(int i = 0; i < n; ++i) Arg[A[i]] = i;
    while(q--){
        char c; std::cin >> c;
        if(c == '1'){
            int s, t; std::cin >> s >> t; --s; --t;
            const int vs = LST.fold_at(s), vt = LST.fold_at(t);
            LST.assign_at(s, vt); LST.assign_at(t, vs);
            Arg[vt] = s; Arg[vs] = t;
        }
        else{
            int s, t; std::cin >> s >> t; --s;
            const int v = LST.fold_range(s, t);
            std::cout << Arg[v] + 1 << '\n';
        }
    }
    return 0;
}
0