题解

给定一个长度为$n$的排列，有两种操作，分别为区间取$mex$与交换两个相邻位置的元素。

考虑到所给序列是一个排列，所以$0~n-1$的每个元素要么在查询区间中出现，要么在区间外出现，所以区间内最小未出现的元素即区间外的最小元素（当区间包含整个序列时，答案应为$n$，没有在区间外出现，这种情况特判即可）。记录前缀后缀最小值，查询时答案即为$min(mnl[l-1],mnr[r+1])$。当交换相邻元素时，只有这两个相邻位置的前缀后缀最小值可能会发生改变。所以整体复杂度为$O(n+Q)$

（由排列区间取$mex$转化为区间外取$min$和后继状态存在偏序关系的$SG$函数计算转化为取$max$可知，$SG$函数复杂的$mex$运算可以通过问题的性质化为更简单的$min/max$操作）