LargeDumpling

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

LYDSY 2453 维护队列

传送门

        看了黄学长题解后来做这道题,转化后是和上一道题差不多,但是转化过程不容易想到(如果不看题解我能做出来吗?估计不行吧  Drz)。

        怎么转化呢,每一个点记录前一个和它颜色相同的位置标号,然后对于求[l,r]区间内有多少种颜色,即是求[l,r]区间内有多少个点记录的标号小于l。转化思想容易理解,但是不容易想到。

分块做法

        本题的修改和查询是很容易实现的。本以为修改操作只有最多1000次,每次重新计算应该是兹辞的,没想到居然不兹辞,为此纠结了一晚上。以为是自己哪里写错了(虽然Datamaker确实写做了,不过应该不影响?),结果把Datamaker的错改了之后,还是TLE了。

        之后细读黄学长代码发现,黄学长只重新计算了标号发生变动的块。想想看,黄学长这样每次修改应该是要比我快BLOCK_NUMBER倍的。

评论

© LargeDumpling | Powered by LOFTER