[传送门]
比赛的时候想了半天的带修改主席树(其实之前只写过一次。)，两个log甚至三个log都想了，自闭了五个小时还是不会实现。问了一下西瓜得到了一个非常妙的1 log解法。此处膜瓜??
一操作相当于把一个数删掉，因为$a_i + 10^7$肯定不会影响到$n + 1$，最坏情况下也能直接取$n + 1$。
2操作就是询问$\left[1, r\right]$中大于等于$k$并且没出现过的最小的数，即求大于等于$k$的mex。 转化一下问题，记$b$序列，$b[i]$表示$i$这个数在$a$序列中出现的位置。然后2操作就相当于在$b$序列的区间$\left[k, n\right]$中查第一个大于$r$的数，也就是求最大的$i$满足$\left[k,i\right]$的值均小于等于$rr$(用$rr$和下面区间查询的$r$作区分)并且$b_i$大于$rr$。
那么就建一棵线段树维护$b$的区间最大值，一操作删一个数就把它在$b$中的值设为$inf$表示这个数可以使用了。
查询的时候，如果查询到单点的地方，看单点这个值是不是比$rr$小，如果比$rr$小的话，就返回当前的位置$l$，否则返回$0$，表示这个节点的值已经比$rr$大了。
然后，先查左子树，如果左子树返回的值等于$mid$，则说明左子树的值均可以使用，那么就去查右子树，再把左子树与右子树得到的值取$min$，这就是上面为什么在大于$r$的情况要返回0。
但是，这还不够，因为这样有可能左子树可以用，我又得去查右子树，所以可以被卡成$O(n^2)$
要加点剪枝，如果当前区间为$\left[l, r\right]$,要查询的区间为$\left[x, y\right]$，如果$\left[l, r\right]$被$\left[x, y\right]$包含了并且当前的值小于$rr$，直接返回区间右端点$r$就可以了。 这种神奇的区间查询第一次见，说起来还是比较麻烦，具体看代码就应该可以了。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int n, m, a[N], b[N]; struct Seg { #define lp p << 1 #define rp p << 1 | 1 int tree[N << 2]; inline void pushup(int p) { tree[p] = max(tree[lp], tree[rp]); } void build(int p, int l, int r) { tree[p] = 0; if (l == r) { tree[p] = b[l]; return; } int mid = l + r >> 1; build(lp, l, mid); build(rp, mid + 1, r); pushup(p); } void update(int p, int l, int r, int pos) { if (l == r) { tree[p] = N; return; } int mid = l + r >> 1; if (pos <= mid) update(lp, l, mid, pos); else update(rp, mid + 1, r, pos); pushup(p); } int query(int p, int l, int r, int x, int y, int val) { if (x > y) return 0; if (l == r) { if (tree[p] <= val) return l; return 0; } if (x <= l && y >= r && tree[p] <= val) return r; int mid = l + r >> 1; if (x <= mid) { int temp = query(lp, l, mid, x, y, val); if (temp == mid) return max(temp, query(rp, mid + 1, r, x, y, val)); else return temp; } return query(rp, mid + 1, r, x, y, val); } } seg; int main() { int T; scanf("%d", &T); while (T--) { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[a[i]] = i; seg.build(1, 1, n); int ans = 0; while (m--) { int opt; scanf("%d", &opt); if (opt == 1) { int t1; scanf("%d", &t1); t1 ^= ans; //cout << "t1 = " << t1 << endl; seg.update(1, 1, n, a[t1]); } else { int r, k; scanf("%d%d", &r, &k); r ^= ans, k ^= ans; //cout << "r = " << r << " k = " << k << endl; ans = seg.query(1, 1, n, k, n, r); if (ans == 0) ans = k; else ans++; printf("%d\n", ans); } } } return 0; }
原文：https://www.cnblogs.com/Mrzdtz220/p/11673021.html
