#include #include #include #include #include #include #include #include template 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 std::ostream& operator << (std::ostream& os_arg, const std::vector& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); } template std::ostream& operator << (std::ostream& os_arg, const std::array& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); } template std::ostream& operator << (std::ostream& os_arg, const std::pair& pair_arg){ return os_arg << '(' << pair_arg.first << ", " << pair_arg.second << ')'; } #ifndef ONLINE_JUDGE template void dump_out(Head head_arg){ std::cerr << head_arg << '\n'; } template 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 true // '''''''''''''''''''''''''''''''''''''''''''''''''''''''''' // 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 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; const int arr_len; // 扱う配列の長さ n const int height; // セグメント木の高さ : 要素数 2^k の k const int length; // セグメント木の要素数 : 2^k (dataの数は 2 * 2^k) std::vector data; // 要素の部分 std::vector 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& 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 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 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 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::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 A(n); for(auto& itr : A){ std::cin >> itr; --itr; } LazySegmentTree LST(A.cbegin(), A.cend()); std::vector 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; }