2020-2021:teams:farmer_john:2020hdu暑期多校第二场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020hdu暑期多校第二场 [2020/08/07 17:42] jjleo [B.] |
2020-2021:teams:farmer_john:2020hdu暑期多校第二场 [2020/10/07 21:24] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======比赛名称====== | + | ======2020HDU暑期多校第二场====== |
| [[https://codeforces.com/gym/288624|比赛链接]] | [[https://codeforces.com/gym/288624|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 55: | 行 55: | ||
| 考虑函数不增不删只有数次询问的情况，可以发现这些函数都是$f(x)=x^4$进行平移得来，两两只会相交一次并在此处改变大小关系，因此可以类似决策单调性dp中的二分栈，维护出每个区间的最优函数，对于每个询问只需二分找到对应区间即可获得答案。但本题有函数的增删，因此可以再套一个线段树分治，对每一层都来一次上述过程，处理区间中所有的询问，而每个询问只需取最小值即可。这样每个询问被处理$O(\log n)$次，每个函数被处理$O(\log n)$次，总复杂度$O(n \log ^2 n)$。（一开始把所有函数和询问全在叶子节点处理，直接白分治了） | 考虑函数不增不删只有数次询问的情况，可以发现这些函数都是$f(x)=x^4$进行平移得来，两两只会相交一次并在此处改变大小关系，因此可以类似决策单调性dp中的二分栈，维护出每个区间的最优函数，对于每个询问只需二分找到对应区间即可获得答案。但本题有函数的增删，因此可以再套一个线段树分治，对每一层都来一次上述过程，处理区间中所有的询问，而每个询问只需取最小值即可。这样每个询问被处理$O(\log n)$次，每个函数被处理$O(\log n)$次，总复杂度$O(n \log ^2 n)$。（一开始把所有函数和询问全在叶子节点处理，直接白分治了） | ||
| =====I.===== | =====I.===== | ||
| - | **upsolved by ** | + | **solved by ** |
| ====题意==== | ====题意==== | ||
2020-2021/teams/farmer_john/2020hdu暑期多校第二场.1596793341.txt.gz · 最后更改: 2020/08/07 17:42 由 jjleo
