置顶更新

2021.1.8

做题：

1）· Luogu P4773

? · 数论，比较正常的找规律题，反正已经会了qwq

? · 已AC（/）

2）· Luogu P5148

? · 还是数论，多项式，暴力拆一遍完事

? · 已AC（/）

3）· Luogu P2575

? · 找点博弈论的题目做一下……这题没有看出来……看了下题解，画个图……没想到阶梯nim题目/kk，被震惊到了

? · 已AC（/）

4）· Luogu P2964

? · 又是博弈论，博弈dp题目，思路感觉还算好想……一开始因为前缀和的问题挂了几发。

? · 已AC（/）

算法学习：

·学了下李超树……之前都没好好看过，昨天的T1感觉好像可以用这个东西来写，然后就去看了一下相关博客……明天写个这个方面的总结。（话说回来博客好像好久又没写了……反省一下。）

（此处为摘抄）

·李超树的具体实现过程：

我们先将每一条线段都表示成点斜式，接下来用\(k\)表示斜率，\(b\)截距。当我们插入一条线段\(y=kx+b\)的到区间\([l,r]\)（插入直线则是\([?inf,inf]\)）时候，我们需要判断这条线段是否可以更新这个这个区间的答案。我们记一条线段\(s\)为优势线段，表示在这个区间\([l,r]\)中的线段中，\(s\)在\(mid=(l+r)>>1\)这个点上的\(y\)的值是最大的。那么插入一条线段的时候，就会出现下面几种情况：

1. 当这个区间还没有优势线段的时候，就可以直接将该线段设成该区间的优势线段，然后返回。
2. 当这个区间已经有优势线段，如果插入线段在区间\([l,r]\)的值都比该优势线段大，那么就可以直接替换掉这个优势线段，然后返回。或者是在区间\([l,r]\)的都比该优势线段小，那么就可以直接返回了。
3. 当这个区间的优势线段\(seg\)和插入线段\(s\)存在某个交点的时候，显然，我们需要更新这个区间的子区间的优势线段的答案。我们假设交点位置为\(pos\)，该区间中点位置为\(mid\)，\(ysegl\),\(ysegr\)表示\(seg\)线段左右两个端点的y值，\([ysl,ysr]\)同理。如果\(ysegl<ysl\),\(ysegr>ysr\)，那么说明在\(pos\)右边为\(seg\)优，\(pos\)左边为\(s\)优，然后判断此时\(pos\)的位置，如果此时\(pos\)的位置在\(mid\)的左边，说明s这条优势线段仍然需要下方到子区间去，然后继续递归下去即可，另一半也是类似的。最后不要忘记更改本区间的优势线段就行了。

查询的话就比较简单了，像普通的线段树一样，如果当前区间在查询区间当中的话，那么就直接返回当前优势线段，否则递归处理，然后顺便和当前区间优势线段的\(y_{seg_{pos}}\)比较一下，返回值更加大的线段就行了。

·复杂度：对于查询每一个点的极值，复杂度都为\(O(log(n))\)。但是插入线段时，因为寻找插入的区间和标记都需要\(O(log(n))\)的时间，所以复杂度会是\(O(log^2(n))\)，最后的总复杂度是\(O(nlog^2(n))\)

·PS一些碎碎念：一般李超树能用上的地方都有什么啊……除了昨天T1那样子的标准的查询……以前好像联赛集训的一道每次算最大直方图的题目也要用李超树，但是真的很难扯上啊……

2021.1.9

做题：

1）· Luogu P1156

? · 背包，md真的想不到，还是要看题解……

? · 已AC（/）

2）· Luogu P2224

? · 毒瘤背包题……

? · 已AC（/）

算法学习：

省选课上的好累……上完课还洗了个头……

回去回顾了一下上次省选课讲的构造知识……
·又是碎碎念：构造题没有固定思维真的难想啊……

把学习笔记写完了。今天干的事情好少……在家里也不能这么颓啊……

置顶更新

原文：https://www.cnblogs.com/linskyQWQ/p/14257193.html