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