-
要开long long
-
数组至少开8倍空间
-
离散化用lower_bound的时候记得要用去重后的数组长度,而不是之前数组的长度或者是乘2后的长度。
-
线段树询问要考虑左右边界:要区分求的是点还是线段
-
进行push_up操作的时候要特判叶子节点的情况。
-
进行push_up操作时要区分当前节点左右儿子和当前节点代表区间左右端点的区别
具体来说:
if (tr[p].cnt)
tr[p].len = val[r + 1] - val[l];
else
tr[p].len = tr[ls(p)].len + tr[rs(p)].len;
总结:20pts的时候,大概率是push_up函数写错了,需要仔细检查(第5个点我调了快2h……)