炸!线段树合并
  • 板块灌水区
  • 楼主Laoshan_PLUS
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/1/21 16:39
  • 上次更新2024/1/21 19:32:15
查看原帖
炸!线段树合并
498837
Laoshan_PLUS楼主2024/1/21 16:39

线段树合并有两种写法,到底有什么区别啊?

个人习惯:

#define lp st[p].lc
#define rp st[p].rc
#define lq st[q].lc
#define rq st[q].rc

写法一:

int merge(int p, int q, int l, int r) {
    if (!p || !q) return p + q;
    if (l == r) {
        st[p].c += st[q].c;
        return p;
    }
    int mid = (l + r) >> 1;
    lp = combine(lp, lq, l, mid);
    rp = combine(rp, rq, mid + 1, r);
    st[p].c = st[lp].c + st[rp].c;
    return p;
}

写法二:

int merge(int p, int q) {
	if (!p || !q) return p + q;
	st[p].c += st[q].c;
	pushdown(p);
	pushdown(q);
	lp = merge(lp, lq);
	rp = merge(rp, rq);
	return p;
}
2024/1/21 16:39
加载中...