package main import ( "bufio" "fmt" "os" ) func main() { // https://yukicoder.me/submissions/845112 // op1:赋值 // !op2:查询区间最小值处的索引(线段树上二分即可) in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, q int fmt.Fscan(in, &n, &q) nums := make([]E, n) for i := range nums { fmt.Fscan(in, &nums[i]) } seg := NewSegmentTree(nums) for i := 0; i < q; i++ { var op, left, right int fmt.Fscan(in, &op, &left, &right) if op == 1 { left-- right-- tmp := seg.Get(left) seg.Set(left, seg.Get(right)) seg.Set(right, tmp) } else { left-- min_ := seg.Query(left, right) res := seg.MaxRight(left, func(x int) bool { return x > min_ }) fmt.Fprintln(out, res+1) } } } const INF int = 1e18 // PointSetRangeMin type E = int func (*SegmentTree) e() E { return INF } func (*SegmentTree) op(a, b E) E { return min(a, b) } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } type SegmentTree struct { n, size int seg []E } func NewSegmentTree(leaves []E) *SegmentTree { res := &SegmentTree{} n := len(leaves) size := 1 for size < n { size <<= 1 } seg := make([]E, size<<1) for i := 0; i < n; i++ { seg[i+size] = leaves[i] } for i := size - 1; i > 0; i-- { seg[i] = res.op(seg[i<<1], seg[i<<1|1]) } res.n = n res.size = size res.seg = seg return res } func (st *SegmentTree) Get(index int) E { if index < 0 || index >= st.n { return st.e() } return st.seg[index+st.size] } func (st *SegmentTree) Set(index int, value E) { if index < 0 || index >= st.n { return } index += st.size st.seg[index] = value for index >>= 1; index > 0; index >>= 1 { st.seg[index] = st.op(st.seg[index<<1], st.seg[index<<1|1]) } } // [start, end) func (st *SegmentTree) Query(start, end int) E { if start < 0 { start = 0 } if end > st.n { end = st.n } if start >= end { return st.e() } leftRes, rightRes := st.e(), st.e() start += st.size end += st.size for start < end { if start&1 == 1 { leftRes = st.op(leftRes, st.seg[start]) start++ } if end&1 == 1 { end-- rightRes = st.op(st.seg[end], rightRes) } start >>= 1 end >>= 1 } return st.op(leftRes, rightRes) } func (st *SegmentTree) QueryAll() E { return st.seg[1] } // 二分查询最大的 right 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MaxRight(left int, predicate func(E) bool) int { if left == st.n { return st.n } left += st.size res := st.e() for { for left&1 == 0 { left >>= 1 } if !predicate(st.op(res, st.seg[left])) { for left < st.size { left <<= 1 if predicate(st.op(res, st.seg[left])) { res = st.op(res, st.seg[left]) left++ } } return left - st.size } res = st.op(res, st.seg[left]) left++ if (left & -left) == left { break } } return st.n } // 二分查询最小的 left 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MinLeft(right int, predicate func(E) bool) int { if right == 0 { return 0 } right += st.size res := st.e() for { right-- for right > 1 && right&1 == 1 { right >>= 1 } if !predicate(st.op(st.seg[right], res)) { for right < st.size { right = right<<1 | 1 if predicate(st.op(st.seg[right], res)) { res = st.op(st.seg[right], res) right-- } } return right + 1 - st.size } res = st.op(st.seg[right], res) if right&-right == right { break } } return 0 }