hdu3308 LCIS
给定10^5个数,区间查询严格上升的最长连续序列长度,点更新某个数.
线段树,区间合并
有三个数组,msum, lsum, rsum,分别存总最长,左端串长,右端串长
一直错的一个地方是:query中,合并的时候,若左右儿子可以合并,应该取max{min[左儿子右长,实际右长],min[右儿子左长,实际左长]},而不是max{min[左儿子最大长,实际右长],min[右儿子最大长,实际左长]}.因为有可能儿子最大长并不是由中间接上的那一段产生的
这种细节非常复杂的题分析清楚算法很重要.靠Debug实在很难找.其实是原理性错误...
#include <cst......
阅读全文