请求添加HACK数据:查询区间的l==r
查看原帖
请求添加HACK数据:查询区间的l==r
441391
myyaner楼主2024/9/28 14:52

由于要查询左闭右开区间[l, r)内的左端点数量,所以当l==r时,调用segtree_query(根节点=1, l, r-1, 左端点)时会出现查询闭区间[l, l-1]的情况。

输入:

4 2
1 1 3
2 1 1

输出:

1

专打线段树查询:

// 查询闭区间[l, r]内的左/右端点数量
int segtree_query(const int root, const int &l, const int &r, const int &type) {
    if(l <= segtree[root].l && r >= segtree[root].r) { return segtree[root].v_sum[type]; }
    int m = (segtree[root].l + segtree[root].r) / 2;\
      
    // 这种方式逃过一劫,l>r时总能保证在叶子节点处时,两个if分支都不执行,从而return 0;
    // int query = 0;
    // if(l <= m) { query += segtree_query(root * 2, l, r, type); }
    // if(r > m) { query += segtree_query(root * 2 + 1, l, r, type); }
    // return query;
      
    // 这种方式无限递归,爆栈
    if(r <= m) { return segtree_query(root * 2, l, r, type); }
    if(l > m) { return segtree_query(root * 2 + 1, l, r, type); }
    return segtree_query(root * 2, l, r, type) + segtree_query(root * 2 + 1, l, r, type);
}
2024/9/28 14:52
加载中...