scoi2010股票交易

⑴ scoi2010 operation哪位高手告訴一下怎麼統計「[a, b]區間內最多有多少個連續的1」

恩，有點難
對於一個線段樹的節點i，維護一個ls代表從左往右數最大的連續1的個數，rs是從右往左數最大連續1個個數，ss是這個節點最大的連續1個個數。如果ss=ls 或者 ss=rc 那麼 ss=0
ss=max(左兒子的ss,右兒子的ss)
if 左兒子的rs>0 並且右兒子的ls>0 那麼 ss=max(ss,左兒子的rs+右兒子的ls)
ls=左兒子的ls if 左兒子全是1 那麼ls=ls+右兒子的ls
rs=右兒子的rs if 右兒子全是1 那麼rs=rs+左兒子的rs