小奇的数列

题目链接

小奇的数列

题解

这个题好有意思啊…

问模意义下的最小子串和


20分\(O(mn^3))\)枚举

枚举所有子串的和

输出


40分\(O(mn^2)\)加前缀和优化的枚举

与20分类似


70分\(O(mp^2)\)加特判加前缀和优化

如果区间范围大于p,那么一定有两个前缀相减等于0的操作

容斥原理..


100分

以上所有特判+前缀和+容斥原理+平衡树找前缀和前驱

建Treap的时候加的是l-r区间内的所有前缀和.

求前驱的时候减去对应的值.

需要求的是(l-r)的区间和
Treap里面存的是(1-r)的和
求前缀的时候减去(1-l)的和就好了

就算出子段和了.

用Treap/Splay/替罪羊树来维护这个最小子段和.

最终时间复杂度下降到\(O(mplogp)\)


By:Wahacer

2017.12.07

12:01

发表评论

电子邮件地址不会被公开。 必填项已用*标注