HDU6703 array [权值线段树]

$array$

题目描述见链接 .

---

$color{red}{正解部分}$

• 对 $1$ 操作, 等价于将对应位置的数字删除, 在下述 权值线段树 中把对应位置权值赋为 $N+1$ 即可 .
• 对 $2$ 操作, 首先可以发现答案 $ans ∈ [1, N+1]$,
  考虑怎么去寻找 $大于等于k且尽量小$ 且 $ans !=a_{[1,r]}$ 的数字,
  建立下标属于 $[1,N+1]$的 权值线段树, 可以保证 $ans$ 一定可以从 权值线段树 中得到,
  权值线段树 的节点存下当前权值区间的 最右位置, 设为 $max\_r$, $N+1$位置的初值为 $N+1$,
  往下递归查找 $[k,N+1]$ 的区间时, 只需要检查 左子树 的 $max\_r$ 是否大于 $r$, 若大于, 说明有解, 往左子树走, 否则只能往 右子树 走 .

---

$color{red}{实现部分}$

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 100005;

int N;
int M;
int A[maxn];
int B[maxn];

struct Segment_Tree{ 

        struct Node{ int l, r, max_r; } T[maxn<<2];

        void Build(int k, int l, int r){
                T[k].l = l, T[k].r = r;
                if(l == r){ T[k].max_r = B[l]; return ; }
                int mid = l+r >> 1;
                Build(k<<1, l, mid), Build(k<<1|1, mid+1, r);
                T[k].max_r = std::max(T[k<<1].max_r, T[k<<1|1].max_r);
        }

        void Modify(int k, int aim_p, int aim_v){
                int l = T[k].l, r = T[k].r;
                if(l == r){ T[k].max_r = aim_v; return ; }
                int mid = l+r >> 1;
                if(aim_p <= mid) Modify(k<<1, aim_p, aim_v);
                else Modify(k<<1|1, aim_p, aim_v);
                T[k].max_r = std::max(T[k<<1].max_r, T[k<<1|1].max_r);
        }

        int Query(int k, int lim, int ql, int qr){
                int l = T[k].l, r = T[k].r;
                if(l == r) return l;
                int mid = l+r >> 1;
                int s = N + 1;
                if(ql <= mid && T[k<<1].max_r > lim) s = Query(k<<1, lim, ql, qr);
                if(s != N+1) return s;
                if(qr > mid && T[k<<1|1].max_r > lim) s = std::min(s, Query(k<<1|1, lim, ql, qr));
                return s;
        }

} seg_t;

void Work(){
        N = read(), M = read();
        for(reg int i = 1; i <= N; i ++) A[i] = read();
        for(reg int i = 1; i <= N; i ++) B[A[i]] = i;
        B[N+1] = N+1;
        seg_t.Build(1, 1, N+1);
        int last_ans = 0;
        for(reg int i = 1; i <= M; i ++){
                int opt = read();
                if(opt == 1){
                        int pos = read() ^ last_ans;
                        if(A[pos] == N+1) continue ;
                        seg_t.Modify(1, A[pos], N+1);
                        A[pos] = N+1;
                }else{
                        int r = read() ^ last_ans, k = read() ^ last_ans;
                        printf("%d
", last_ans = seg_t.Query(1, r, k, N+1));
                }
        }
}

int main(){
        int T_num = read();
        while(T_num --) Work();
        return 0;
}