## 【权值线段树】HDU6703-array

### 传送门

1. 把某个位置的数字+1e7
2. 给定r, k.查询与前r个数字不同的，并且大于等于k的，最小的数字。

#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;
}
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;
}
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);
}
}
}
}