Open ManuShi98 opened 1 year ago
https://manushi98.github.io/2018/07/29/CodeForces%20-%20739C%20Alyona%20and%20towers(%E7%BA%BF%E6%AE%B5%E6%A0%91)/
思路根据题意，我们需要对一个序列执行区间加和计算最长的递增/递减/先增后减序列。对于区间加法，很自然想到线段树，我们考虑线段树维护序列。我们这样考虑，维护一个区间最左端符合条件序列的长度，维护一个区间最右端符合条件序列的长度。push_up的时候用跨过中点的合法序列，左儿子最大值，右儿子最大值一起考虑来更新最大值。在常规序列处理线段树的情况下，我们会发现我们合并时需要左儿子最右端序列的值和右儿子最
https://manushi98.github.io/2018/07/29/CodeForces%20-%20739C%20Alyona%20and%20towers(%E7%BA%BF%E6%AE%B5%E6%A0%91)/
思路根据题意，我们需要对一个序列执行区间加和计算最长的递增/递减/先增后减序列。对于区间加法，很自然想到线段树，我们考虑线段树维护序列。我们这样考虑，维护一个区间最左端符合条件序列的长度，维护一个区间最右端符合条件序列的长度。push_up的时候用跨过中点的合法序列，左儿子最大值，右儿子最大值一起考虑来更新最大值。在常规序列处理线段树的情况下，我们会发现我们合并时需要左儿子最右端序列的值和右儿子最