【模板】线段树

打了一遍P3372的模板线段树

此题是求区间的和,求最小值的线段树也可以同理。把之前的模板修改了一下:

1.简洁了一些:st区间开始,ed区间结束,rt根,addmk延迟标记

2.线段树根节点从1开始,左子树2*rt,2*rt+1,也和之前的堆一致

Read More

【搜索】01迷宫

一看题目标注的高性能就知道不能询问一次搜一次。因为一个联通块的答案是相同的,所以一个块只要搜一次,再标记上就行了。

标记用了个队列记录再一次标记,怕搜晕了……

Read More

【做题笔记】2018.1.20

P1090合并果子

这题和上次只能合并相邻的合并石子不一样,直接贪心就行。然而对效率的要求比较高,于是被科普了一下什么是优先队列……

所以果子堆直接用堆维护了……(果子堆->堆)每一次取最小和次小的两个出来合并(最小的在堆顶,次小的在两个子节点中),维护堆即可。

Read More