题目链接：HDU6703-array
题意：
给定一个长度为n的序列，序列中的元素为1-n，不会重复出现，然后有两个操作：
- 把某个数加上10000000；
- 查询一个数，要求这个数不小于k，且在序列前r个中没出现过，求出这个数的最小值。
题解：
做法一：权值线段树+二分
线段树上的叶子节点保存对应的数在原序列中的位置，若某个数没出现，则赋值为inf，然后维护区间最大值。
对于操作1，可以理解为删除操作，即把相应叶子节点的值改为inf。
对于操作2，可以理解为查询这颗线段树上，[k,n+1]这些叶子节点中，第一个值大于r的节点。
做法二：主席树+set
分析题目可以发现，答案一定是在[1,n+1]这个区间内。
对于操作1，我们可以用set存哪些值是被删除了的。
对于操作2，我们先假定，没有进行过操作1，因为序列元素是1-n且每一个只会出现一次，所以我们可以得到，答案一定是a[r+1,n]中大于等于k的最小值，因为答案可能是n+1，所以我们对原序列进行扩充，第n+1个元素是n+1，然后对于每次询问，我们先找出a[r+1,n+1]中大于等于k的最小值，然后在set中二分出大于等于k的最小值，两者取min即可。
需要注意一点，这道题卡掉了2个log的做法，所以我们不能二分一个答案，然后再去查询，考虑到线段树就是一种二分结构，所以我们直接在查询的过程中进行二分。
参考代码：
/*权值线段树+二分*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
const int inf = 0x3f3f3f3f;
int T;
int n, q;
int sum[MAXN << 2];
int a[MAXN];
void pushup(int rt)
{
sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
if (l == r)
{
sum[rt] = inf;
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
void update(int p, int val, int l, int r, int rt)
{
if (l == r)
{
sum[rt] = val;
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
update(p, val, l, mid, rt << 1);
else if (p > mid)
update(p, val, mid + 1, r, rt << 1 | 1);
pushup(rt);
}
int query_max(int l, int r, int rt, int val)
{
if (l == r)
return sum[rt];
int mid = (l + r) >> 1;
if (val <= mid)
return query_max(l, mid, rt << 1, val);
else
return query_max(mid + 1, r, rt << 1 | 1, val);
}
int query(int R, int K, int l, int r, int rt)
{
if (l == r)
return l;
int mid = (l + r) >> 1;
if (K <= mid && sum[rt << 1] > R)
{
int p = query(R, K, l, mid, rt << 1);
if (query_max(l, r, rt, p) > R)
return p;
}
return query(R, K, mid + 1, r, rt << 1 | 1);
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &q);
build(1, n + 2, 1);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), update(a[i], i, 1, n + 2, 1);
int ans = 0;
while (q--)
{
int op;
scanf("%d", &op);
if (op == 1)
{
int pos;
scanf("%d", &pos);
pos ^= ans;
update(a[pos], inf, 1, n + 2, 1);
}
else
{
int rr, kk;
scanf("%d%d", &rr, &kk);
rr ^= ans;
kk ^= ans;
ans = query(rr, kk, 1, n + 2, 1);
printf("%d\n", ans);
}
}
}
return 0;
}/*主席树+set*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
const int inf = 0x3f3f3f3f;
int T;
int n, q;
int a[MAXN];
set<int> s;
int tot, Tree[MAXN * 40], ls[MAXN * 40], rs[MAXN * 40], sum[MAXN * 40];
void update(int las, int val, int l, int r, int &rt)
{
rt = ++tot;
ls[rt] = ls[las];
rs[rt] = rs[las];
sum[rt] = sum[las] + 1;
if (l == r)
return;
int mid = (l + r) >> 1;
if (val <= mid)
update(ls[las], val, l, mid, ls[rt]);
else
update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int L, int R, int l, int r, int K)
{
if (l == r)
return l;
int lson = sum[ls[R]] - sum[ls[L]];
int rson = sum[rs[R]] - sum[rs[L]];
int mid = (l + r) >> 1;
int res = inf;
if (lson && K <= mid)
res = query(ls[L], ls[R], l, mid, K);
if (res != inf)
return res;
if (rson)
res = query(rs[L], rs[R], mid + 1, r, K);
return res;
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
s.clear();
tot = 0;
for (int i = 1; i <= n; i++)
update(Tree[i - 1], a[i], 1, n + 1, Tree[i]);
update(Tree[n], n + 1, 1, n + 1, Tree[n + 1]);
int ans = 0;
while (q--)
{
int op;
scanf("%d", &op);
if (op == 1)
{
int pos;
scanf("%d", &pos);
pos ^= ans;
s.insert(a[pos]);
}
else
{
int R, K;
scanf("%d%d", &R, &K);
R ^= ans;
K ^= ans;
ans = query(Tree[R], Tree[n + 1], 1, n + 1, K);
auto it = s.lower_bound(K);
if (it != s.end())
ans = min(ans, *it);
printf("%d\n", ans);
}
}
}
return 0;
}