P4137 权值线段树 回滚莫队

题意
传送门 P4137 Rmq Problem / mex
题解
权值线段树
将查询离线，按照右界升序排序后依次处理。权值线段树维护每个元素出现的索引最大的位置，特别的，将 [ 0 , m a x n ) [0,maxn) [0,maxn) 初始化为 1 -1 1。那么对于查询 [ l , r ) [l,r) [l,r)，答案为索引值小于 l l l 的最小值。总时间复杂度 O ( n log n ) O(nlog n) O(nlogn)。
#include
using namespace std;
#define pb push_back
const int MAXN = 2E5 + 5, SZ = 1 << 19; int N, M, A[MAXN], res[MAXN]; struct Query { int l, r, id; bool oper

P4137 权值线段树 回滚莫队最先出现在Python成神之路。