admin 管理员组

文章数量: 1087749

2018 ccpc吉林 H Lovers（线段树）

硬核线段树

现在无处补题，输入输出的格式也都忘记了，无法贴代码，先捏一个思路。

大意就是每次对于一个区间对这个区间的数字字符串的左边和右边都加上一个同一个数字，询问操作是对区间求和。

当时觉得这个题目没有什么思路，就放弃了这道硬核线段树，今天贤神在群里列了一下公式，还是有一点可惜。

思路具体如下：

1.维护两颗线段树：

sum2(k,l,r)= 10^len[ai],  (l<=i<=r) 

sum1(k,l,r)= ai, (l<=i<=r)

2.每次的更新：

sum2(k,l,r)=sum2(k,l,r)*10^2

sum1(k,l,r)=sum1(k,l,r)*10+sum2*d+d*(r-l+1)

3.询问即正常的线段树询问

 

这个辅助线段树建的妙啊，tql

感觉题目无从下手的时候，努力找到一点点和套路相似的感觉还是有助于解题的。比如本题钟对的10的幂次和，是可以直接一直乘十的不受影响量，就可以用线段树十分简单的处理。

本文标签： 2018 ccpc吉林 H Lovers（线段树）

版权声明：本文标题：2018 ccpc吉林 H Lovers（线段树） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1699085914a327347.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。