LargeDumpling

我只负责打字,内容我也不知道从何而来。

LYDSY 3343 教主的魔法

传送门

        题意让维护一个长度不超过1000000数列,可以区间修改(加/减 一个不超过1000的数),也会问你某个区间中不小于给定的一个数的数有多少个。操作不超过3000个,数列中的数初始不超过1000。

        问了问HugeGun和红太阳,得到的回答是树套树,不会啊Drz。

        其实是可以用块状数组的,不过看了看1000000的数据范围,本还以为会过不了,又看了看时限,1000000也可搞?

分块做法

        唔,就是分块搞搞啦。先把数组备份一遍,然后对每一块内部进行排序。

        修改操作,对于一整块可以直接打标记(打在块首上?我是这么想的),不是整块的就强行搞然后重新对那块进行排序。

        查询操作,对于某一块查询时,要根据该块的标记进行调整。对于一整块,可以在排序后的数组中二分,不是整块的就强行搞好了。


        暂时还不会树套树,等会树套树了之后再来试试用树套树搞搞?

        在打这份分块代码的时候,第一次居然忘了调用初始化函数,使算法退化成了暴力,然后两个暴力程序在小数据下拍的不亦乐乎。

        附上暴力代码和Datamaker?我才不嘞,这么简单自己写就好。

评论

© LargeDumpling | Powered by LOFTER