NOIp2018停课刷题记录

Preface

老叶说了高中停课但是初中不停的消息后我就为争取民主献出一份力量

其实就是和老师申请了下让我们HW的三个人听课结果真停了

那么还是珍惜这次机会好好提升下自己吧不然就\(AFO\)了

• Luogu P4198 楼房重建 把高度化为斜率，然后就是个动态最长上升子序列的问题了，线段树上二分即可解决，而且可以做到\(O(n\log n)\)
• NOIP模拟赛10.24 实力翻车，T1主席树裸题切了，T2想了贪心+前缀和+二分正解，最后1min写完发现忘记判边界了炸到60，T3以为很难所以弃了XRYdalao说这是整套题里最水的一道，又被狂踩了
• Luogu P4169 [Violet]天使玩偶/SJY摆棋子 时间很多下午改完题目就准备学下KD-Tree据说是骗分神器。听说这是板子题就来做，没想到还要替罪羊树思想重构的。结果花了一个下午调试。结果\(\max\)写错了
• Luogu P2633 Count on a tree 主席树+树上差分。看到第\(k\)大一眼主席树维护，考虑从根到子树路径差分，我们维护\(u,v,LCA_{u,v},father_{LCA_{u,v}}\)即可查询
• Luogu P3302 [SDOI2013]森林 询问和上一题一样，考虑连边的过程貌似要LCT维护。但是这样主席树就不好搞。我们看一下数据范围\(n\le80000\)，显然是放\(O(\log^2)\)的做法。那么我们只需要启发式合并两棵主席树即可。

NOIp2018停课刷题记录

原文：https://www.cnblogs.com/cjjsb/p/9852964.html