线段树合并有两种写法,到底有什么区别啊?
个人习惯:
#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;
}