题意
给一个(1)到(n)的排列
现在有(m)个操作，每个操作是下面的一种：
- ((1,pos))，指把(pos)位上的数增加(10,000,000)
- ((2,r,k))，询问操作，你需要输出一个数满足下列三个条件
- 这个数不等于(a_i(1leq i leq r))中的任意一个
- 这个数不小于(k)
- 是满足上两个条件的数中的最小的一个
(Tleq 10,1leq n leq 10^5, 1leq m leq 10^5 ,1leq kleq n)
本题强制在线
解法
考场上头铁，硬肝了(4h)
结考后(20)分钟调出来，(1A...)但想出来还是很高兴的
我们会发现每次给出的(k)都在([1,n])范围内，那么我们操作二中输出的数最大也就是(n+1)
所以给(pos)位上的数加上(10^7)实际上相当于把这个数从排列中删除
我们主要看第二个操作
对于(2,3)两个条件，我们能够很快想到权值线段树维护
每次在权值线段树中查询([k,n])，在满足条件(1)的情况下尽量往左走即可
那么我们怎么判断是否满足条件(1)呢？
我们可以发现条件(1)是关于位置的限制，所以我们在权值线段树中存储各个元素的位置并维护其最大值
那么在查询时按照以下的顺序即可：
如果左子树的位置最大值(geq r)，证明左子树中一定有满足条件的数，向左子树查询
否则如果右子树的最大值(geq r)，向右子树查询
如果左右子树都没有，返回一个极大值
在所有查询结果中取一个最小值即可
对于删除操作，直接把其位置设为一个极大值，因为只要询问区间包含这个数，这个数必然是合法的
代码
没封装，有点丑。。。
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
const int add = 10000000;
int T, n, m, lstans;
int a[N], b[N], mx[N << 2];
inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x < y ? x : y; }
void build(int root, int l, int r) {
if (l == r) {
mx[root] = b[l];
return;
}
int mid = l + r >> 1;
build(root << 1, l, mid);
build(root << 1 | 1, mid + 1, r);
mx[root] = max(mx[root << 1], mx[root << 1 | 1]);
}
void change(int root, int l, int r, int x) {
if (l == r) {
mx[root] = 0x7fffffff;
return;
}
int mid = l + r >> 1;
if (x <= mid)
change(root << 1, l, mid, x);
if (x > mid)
change(root << 1 | 1, mid + 1, r, x);
mx[root] = max(mx[root << 1], mx[root << 1 | 1]);
}
int query(int root, int l, int r, int x, int y, int v) {
if (r < x || l > y) return 0x7fffffff;
if (l == r) return l;
int res = 0x7fffffff, mid = l + r >> 1;
if (mx[root << 1] > v)
res = min(res, query(root << 1, l, mid, x, y, v));
if (res == 0x7fffffff && mx[root << 1 | 1] > v)
res = min(res, query(root << 1 | 1, mid + 1, r, x, y, v));
return res;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
for (int i = 1; i <= n; ++i) b[a[i]] = i;
build(1, 1, n);
lstans = 0;
int op, t1, t2, t3;
while (m--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d", &t1);
t1 ^= lstans;
change(1, 1, n, a[t1]);
} else {
scanf("%d%d", &t2, &t3);
t2 ^= lstans, t3 ^= lstans;
lstans = query(1, 1, n, t3, n, t2);
if (lstans == 0x7fffffff) lstans = n + 1;
printf("%d
", lstans);
}
}
}
return 0;
}