hdu6703 array(线段树)

题目链接
大意：给你一个1-n的排列，然后支持两种操作

1. l ,给x这个位置加上1e7
2. l r,询问1-r位置上没出现过且大于等于r的最小值
   思路：我们建一颗权值线段树，维护区间元素的最大位置；
   首先答案肯定在1-n+1中，所以对于修改操作来说 直接单点修改成一个极大的值。
   询问操作我们直接询问r-n+1的元素出现在>l位置中的最小元素即可。
   因为是最小值所以我们在递归的过程中，先搜小的，搜到就直接返回即可，不然会超时。
   细节见代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
int T, n, m;
int t[N << 2], Q[N << 2];
int a[N], b[N];
#define ls o<<1
#define rs o<<1|1
#define mid (l+r>>1)
//查询k+1-n+1 第一个>r的x
void build(int o, int l, int r) {
    if (l == r) {
        t[o] = b[l];
        return ;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    t[o] = max(t[ls], t[rs]);
}
void u(int o, int l, int r, int k, int d) {
    if (l == r) {
        t[o] = d;
        return ;
    }
    if (k <= mid)u(ls, l, mid, k, d);
    else u(rs, mid + 1, r, k, d);
    t[o] = max(t[ls], t[rs]);
}
int get(int o, int l, int r, int x, int y, int k) {
    if (x <= l && y >= r) {
        if (l == r) {
            return l;
        }
    }
    int ans = n + 2;
    if (x <= mid && t[ls] > k) {
        ans = min(ans, get(ls, l, mid, x, y, k));
    }
    if (y > mid && t[rs] > k && ans == n + 2) {
        ans = min(ans, get(rs, mid + 1, r, x, y, k));
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    // freopen("1.in", "r", stdin);
    for (cin >> T; T; T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)cin >> a[i], b[a[i]] = i;
        a[n + 1] = n + 1;
        b[n + 1] = n + 1;
        n++;
        build(1, 1, n);
        int last = 0;
        for (int i = 1; i <= m; i++) {
            int o, l, r;
            cin >> o;
            if (o == 1) {
                cin >> l;
                l ^= last;
                u(1, 1, n, a[l], 1e9);
            } else {
                cin >> l >> r;
                l ^= last;
                r ^= last;
                last = get(1, 1, n, r , n + 1, l);
                cout << last << '\n';
            }
        }
    }
    return 0;
}