传送门

题意是说给定一个排列，长度1e5，要求支持两种操作：
1. 把某个位置的数字+1e7
2. 给定r, k.查询与前r个数字不同的，并且大于等于k的，最小的数字。

经过分析，答案最大不可能超过n+1。这样的话，操作1其实相当于把这个数字从排列中删去。

用两棵权值线段树，每个点上存的是位置。

对每次2操作，在[k,n]区间里找最靠左的并且val[x]大于r的数。

对每次1操作，最开始是初始化一颗每个点值都是n+1的权值线段树，删掉一个数代表这个数字在区间内可以被使用了。所以在线段树上把点改为该位置。

同时2操作也要找[k,n]区间里最靠左而且val2[x]小于等于r的数。

两个数取最小就是答案。

同时还需记录区间最大最小值，以用来在查询的时候剪枝。

没有这个剪枝，查询会退化为n^2log(n)的，因为区间里可能每个数都会递归到底。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define min(a,b) (a)<(b)?(a):(b)
const int maxn = 1e5 + 233;

struct Node{
    int l, r, v;
}t1[maxn * 4], t2[maxn * 4];
int a[maxn], pos[maxn];
int n;
void build(int p, int l, int r)
{
    if(l == r)
    {
        t1[p].l = l, t1[p].r = r, t1[p].v = n + 1;
        t2[p].l = l, t2[p].r = r, t2[p].v = pos[l];
        return ;
    }
    t1[p].l = t2[p].l = l, t1[p].r = t2[p].r = r;
    int mid = (l + r) >> 1;
    build(ls(p), l, mid); build(rs(p), mid + 1, r);
    t1[p].v = min(t1[ls(p)].v, t1[rs(p)].v);
    t2[p].v = max(t2[ls(p)].v, t2[rs(p)].v);
}
void update(int p, int l, int v)
{
    if(t1[p].l == t1[p].r)
    {
        t1[p].v = v;
        return;
    }
    int mid = (t1[p].l + t1[p].r) >> 1;
    if(l <= mid) update(ls(p), l, v);
    else update(rs(p), l, v);
    t1[p].v = min(t1[ls(p)].v, t1[rs(p)].v);
}
int ask1(int p, int l, int r, int v)
{
    if(t1[p].l == t1[p].r)
    {
        if(t1[p].v <= v) return t1[p].l;
        else return n + 1;
    }
    if(l <= t1[p].l && r >= t1[p].r)
    {
        if(t1[p].v > v) return n + 1;
    }
    int mid = (t1[p].l + t1[p].r) >> 1;
    if(r <= mid) return ask1(ls(p), l, r, v);
    if(l > mid) return ask1(rs(p), l, r, v);
    int val = ask1(ls(p), l, r, v);
    if(val != n + 1) return val;
    return ask1(rs(p), l, r, v);
}
int ask2(int p, int l, int r, int v)
{
    if(t2[p].l == t2[p].r)
    {
        if(t2[p].v >= v) return t2[p].l;
        else return n + 1;
    }
    if(l <= t2[p].l && r >= t2[p].r)
    {
        if(t2[p].v < v) return n + 1;
    }
    int mid = (t2[p].l + t2[p].r) >> 1;
    if(r <= mid) return ask2(ls(p), l, r, v);
    if(l > mid) return ask2(rs(p), l, r, v);
    int val = ask2(ls(p), l, r, v);
    if(val != n + 1) return val;
    return ask2(rs(p), l, r, v);
}
int main()
{
    int T; cin >> T;
    while(T--)
    {
        int m;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]] = i;
        build(1, 1, n);
        int ans = 0;
        int o, r, k; 
        while(m--)
        {
            scanf("%d", &o);
            if(o == 1)
            {
                scanf("%d", &k);
                k ^= ans;
                update(1, a[k], k);
            }
            else
            {
                scanf("%d%d", &r, &k);
                r ^= ans, k ^= ans;
                ans = ask1(1, k, n, r);
                if(r < n) ans = min(ans, ask2(1, k, n, r + 1));
                printf("%d\n", ans);
            }
        }
    }
}