题目大意：给定一个 N 个数字的排列，需要支持两种操作：对某个位置的数字 + 1e7，查询区间 [1, r] 中最小的不等于区间中任何一个数字的数。
题解：本题证明了对于 50W 的数据来说，(O(nlog^2n)) 的算法是过不去的。。
首先，最暴力的做法就是树状数组套权值线段树，实现了支持单点修改的主席树功能，但是复杂度爆炸了。
- 题目中所给的排列这一条件，可知没有两个数字是相同的。
- 由于询问的 k 小于 N，因此单点修改操作可以看成是删除了那个位置的数字。因此，可以发现答案一定在区间 [k, n + 1] 中。
解法1：
利用性质一，在序列上建立主席树，并增加一个 set，用来记录所有被删除的数字。每次询问时，可以询问区间 [r + 1, n + 1] 中大于 K 的最小值是多少，同时，在 set 中也二分一个大于 k 的最小值。可知，两者中最小的就是答案。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, a[maxn];
set<int> s;
struct node {
#define ls(o) t[o].lc
#define rs(o) t[o].rc
int lc, rc, sz;
} t[maxn * 20];
int tot, rt[maxn];
void insert(int &o, int p, int l, int r, int pos) {
o = ++tot;
t[o] = t[p];
if (l == r) {
t[o].sz++;
return;
}
int mid = l + r >> 1;
if (pos <= mid) {
insert(ls(o), ls(p), l, mid, pos);
} else {
insert(rs(o), rs(p), mid + 1, r, pos);
}
t[o].sz = t[ls(o)].sz + t[rs(o)].sz;
}
int query(int o, int p, int l, int r, int k) {
if (l == r) {
return l;
}
int mid = l + r >> 1;
int lsz = t[ls(o)].sz - t[ls(p)].sz, rsz = t[rs(o)].sz - t[rs(p)].sz;
int ret = -1;
if (k <= mid && lsz != 0) {
ret = query(ls(o), ls(p), l, mid, k);
}
if (ret != -1) {
return ret;
}
if (rsz != 0) {
ret = query(rs(o), rs(p), mid + 1, r, k);
}
return ret;
}
void read() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
insert(rt[i], rt[i - 1], 1, n + 1, a[i]);
}
insert(rt[n + 1], rt[n], 1, n + 1, n + 1);
}
void solve() {
int lastans = 0;
while (m--) {
static int opt;
scanf("%d", &opt);
if (opt == 1) {
static int pos;
scanf("%d", &pos);
pos ^= lastans;
s.insert(a[pos]);
} else {
static int r, k;
scanf("%d %d", &r, &k);
r ^= lastans, k ^= lastans;
int ret = query(rt[r], rt[n + 1], 1, n + 1, k);
auto it = s.lower_bound(k);
if (it != s.end()) {
ret = min(ret, *it);
}
printf("%d
", ret);
lastans = ret;
}
}
}
void initial() {
for (int i = 1; i <= tot; i++) {
t[i].lc = t[i].rc = t[i].sz = 0;
}
for (int i = 1; i <= n + 1; i++) {
rt[i] = 0;
}
tot = 0;
s.clear();
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
initial();
read();
solve();
}
return 0;
}
解法二：
根据性质二，可知答案区间一定是连续的。考虑建立权值线段树，维护序列下标的最大值。对于每次查询，转化成查询区间 [k, n + 1] 中下标大于 r 的最小权值。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, a[maxn];
struct node {
#define ls(o) t[o].lc
#define rs(o) t[o].rc
int lc, rc, mx;
} t[maxn << 1];
int tot, rt;
inline void pull(int o) {
t[o].mx = max(t[ls(o)].mx, t[rs(o)].mx);
}
void insert(int &o, int l, int r, int pos, int val) {
if (o == 0) {
o = ++tot;
}
if (l == r) {
t[o].mx = val;
return;
}
int mid = l + r >> 1;
if (pos <= mid) {
insert(ls(o), l, mid, pos, val);
} else {
insert(rs(o), mid + 1, r, pos, val);
}
pull(o);
}
void modify(int o, int l, int r, int pos) {
if (l == r) {
t[o].mx = 1e9;
return;
}
int mid = l + r >> 1;
if (pos <= mid) {
modify(ls(o), l, mid, pos);
} else {
modify(rs(o), mid + 1, r, pos);
}
pull(o);
}
int query(int o, int l, int r, int x, int y) { // x -> [x, n + 1] y -> >= y
if (l == r) {
return l;
}
int mid = l + r >> 1;
int ret = -1;
if (x <= mid && t[ls(o)].mx >= y) {
ret = query(ls(o), l, mid, x, y);
}
if (ret != -1) {
return ret;
}
if (t[rs(o)].mx >= y) {
ret = query(rs(o), mid + 1, r, x, y);
}
return ret;
}
void read() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
insert(rt, 1, n + 1, a[i], i);
}
a[n + 1] = n + 1;
insert(rt, 1, n + 1, n + 1, n + 1);
}
void solve() {
int lastans = 0;
while (m--) {
static int opt;
scanf("%d", &opt);
if (opt == 1) {
static int pos;
scanf("%d", &pos);
pos ^= lastans;
modify(rt, 1, n + 1, a[pos]);
} else {
static int r, k;
scanf("%d %d", &r, &k);
r ^= lastans;
k ^= lastans;
lastans = query(rt, 1, n + 1, k, r + 1);
printf("%d
", lastans);
}
}
}
void initial() {
for (int i = 1; i <= tot; i++) {
t[i].lc = t[i].rc = t[i].mx = 0;
}
rt = tot = 0;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
initial();
read();
solve();
}
return 0;
}