警钟长鸣:如果线段树过样例但全WA,存储l和r现算区间长度
查看原帖
警钟长鸣:如果线段树过样例但全WA,存储l和r现算区间长度
441391
myyaner楼主2024/9/25 00:05

query()中合并左右两个查询结果时,需要计算左查询区间的长度的奇偶性。左查询区间的长度由其左右端点下标得到。警惕下标的计算步骤

SegTree segtree_range_query(const int root, const int &l, const int &r) {
    if(l <= segtree[root].l && r >= segtree[root].r) { return segtree[root]; }
    int m = (segtree[root].l + segtree[root].r) / 2;
    if(r <= m) { return segtree_range_query(root * 2, l, r); }
    if(l > m) { return segtree_range_query(root * 2 + 1, l, r); }
    const SegTree query_l = segtree_range_query(root * 2, l, r), query_r = segtree_range_query(root * 2 + 1, l, r);
    SegTree query;
	query.v_lsum = query_l.v_lsum; query.v_rsum = query_l.v_rsum;
    query.l = std::max(segtree[root].l, l); // 易错点
    query.r = std::min(segtree[root].r, r); // 易错点
    // 错误写法: if((m - segtree[root].l + 1) % 2 == 1) {
    // 错误写法: if((m - l + 1) % 2 == 1) {
    // 正确写法: if((m - std::max(segtree[root].l, l) + 1) % 2 == 1) {
    if((query_l.r - query_l.l + 1) % 2 == 1) { // 正确写法
        query.v_lsum ^= query_r.v_rsum;
        query.v_rsum ^= query_r.v_lsum;
    } else {
        query.v_lsum ^= query_r.v_lsum;
        query.v_rsum ^= query_r.v_rsum;
    }
    return query;
}

2024/9/25 00:05
加载中...