贴一个查前驱后继的错误

区间查前驱后继，这里写的是线段树套平衡树，但是只要外层是线段树二分，这样写就错了（其实一开始没这样写，写树状数组套线段树时想到了这个写法，但是那个东西太丑了所以改成线段树套平衡树来做错误示范）

错误写法

CPP

int query_pre(int ql, int qr, int k, int p, int l = 0, int r = MAX){
    if(l == r){
        if(!treap::query(tr[p].rt, ql, qr)) return -INT_MAX;
        return l;
    }
    int mid = (l + r) >> 1;
    if(k <= mid + 1) return query_pre(ql, qr, k, tr[p].ls, l, mid);
    if(treap::query(tr[tr[p].rs].rt, ql, qr)){
        return query_pre(ql, qr, k, tr[p].rs, mid + 1, r);
    }
    return query_pre(ql, qr, k, tr[p].ls, l, mid);
}
int query_nxt(int ql, int qr, int k, int p, int l = 0, int r = MAX){
    if(l == r){
        if(!treap::query(tr[p].rt, ql, qr)) return INT_MAX;
        return l;
    }
    int mid = (l + r) >> 1;
    if(k >= mid) return query_nxt(ql, qr, k, tr[p].rs, mid + 1, r);
    if(treap::query(tr[tr[p].ls].rt, ql, qr)){
        return query_nxt(ql, qr, k, tr[p].ls, l, mid);
    }
    return query_nxt(ql, qr, k, tr[p].rs, mid + 1, r);
}

正确写法

CPP

int query_pre(int ql, int qr, int k, int p, int l = 0, int r = MAX){
    if(!treap::query(tr[p].rt, ql, qr)) return -INT_MAX;
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(k <= mid + 1) return query_pre(ql, qr, k, tr[p].ls, l, mid);
    int res = query_pre(ql, qr, k, tr[p].rs, mid + 1, r);
    if(res == -INT_MAX) return query_pre(ql, qr, k, tr[p].ls, l, mid);
    return res;
}
int query_nxt(int ql, int qr, int k, int p, int l = 0, int r = MAX){
    if(!treap::query(tr[p].rt, ql, qr)) return INT_MAX;
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(k >= mid) return query_nxt(ql, qr, k, tr[p].rs, mid + 1, r);
    int res = query_nxt(ql, qr, k, tr[p].ls, l, mid);
    if(res == INT_MAX) return query_nxt(ql, qr, k, tr[p].rs, mid + 1, r);
    return res;
}

拿前驱举例，第一种写法是判断了“右子树与答案区间有交”后，只要右子树有值，就往右递归，但“右子树有值”不代表“右子树与答案区间的交中有值”，因此就寄了。正确写法应该是先尝试往右递归，看是否有答案，否则往左递归。

贴一个查前驱后继的错误

讨论操作

回复

相关推荐

贴一个查前驱后继的错误