2019CCPC网络赛——array（权值线段树）

题目地址

题意

两种操作

1. 给 a[i] + 10000000

2. 查找不存在 在a[1 ~ r] 中 且不低于k的数

思路

在第一个操作时 由于k的范围不够 就相当于把 a[i] 删除掉即a[i]的下标变为无穷大而对于第二种操作 也就是 等价为在 k之后 的下标的大于r 的可以使用权值线段树用来维护当前区间最大的 下标如果当前的右端点 大于等于k 且 且最大下标大于 r 那就可以在这个区间中查找但是不一定这个区间存在 因为也有可能是 在 小于k的那段而且 下标是 由低到高 所以 能左边 最好左边最好 返回的不是该点的下标 而是这个点所以 也就是这个l,r

代码

#include<iostream>

using namespace std;
const int N = 1e5+10,INF = 0x3f3f3f3f;
struct Node{
    int l,r;
    int maxp;
}tr[N * 4];
int a[N],id[N];
int n,m;
void pushup(int u){
    tr[u].maxp = max(tr[u<<1].maxp,tr[u<<1|1].maxp);
}
void build(int u,int l,int r){
    tr[u] = {l,r};
    if(l == r){
        tr[u].maxp = id[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u<<1,l,mid);
    build(u<<1|1,mid + 1,r);
    pushup(u);
}
void modify(int u,int k){
    if(tr[u].l == tr[u].r){
        tr[u].maxp = INF;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(k <= mid) modify(u<<1,k);
    else modify(u<<1|1,k);
    pushup(u);
}
int query(int u,int k,int r){
    if(tr[u].l == tr[u].r){
        if(tr[u].maxp > r)
            return tr[u].l;
        else return -1;
    }
    int ans = -1;
    int mid = (tr[u].r + tr[u].l) >> 1;
    if(k <= mid && tr[u<<1].maxp > r)
        ans = query(u<<1,k,r);
    if(ans != -1) return ans;
    if(tr[u<<1|1].r>=k&&tr[u<<1|1].maxp > r)
        ans = query(u<<1|1,k,r);
    return ans;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i = 1;i<=n;i++){
            scanf("%d",&a[i]);
            id[a[i]] = i;
        }
        build(1,1,n);
        int ans = 0;
        while(m--){
            int op;
            scanf("%d",&op);
            if(op == 1){
                int x;
                scanf("%d",&x);
                x ^= ans;
                modify(1,a[x]);
            }
            else{
                int k,r;
                scanf("%d%d",&r,&k);
                k ^= ans,r ^= ans;
                ans = query(1,k,r);
                if(ans == -1)
                    ans = max(n + 1,k);
                printf("%d\n",ans);
            }
        }
    }
    
    return 0;
}