- 2024-10-04【题解】「CF765F」Souvenirs
https://www.luogu.com.cn/problem/CF765F首先有一个比较navie的\(O(n\sqrtm\logn)\)的做法(add和del的时候,用两个multiset维护一下。有一个bitset的做法来优化用multiset查询前驱后继的做法:https://www.luogu.com.cn/article/zcmco6hd首先考虑离线下来,将询问挂
- 2024-01-27CF765F Souvenirs 题解
题目链接:CF或者洛谷想了很久,然后想起做过的一道题:秃子酋长,一开始以为差不多,结果写着写着就发现不对劲了。最后写出了个神仙回滚莫队解法,感觉很妙,记录下。进入神仙分析时刻首先,我们来考虑一个事实,加上一个数以后,如果能找到它的前后驱,那么可以立马更新最优解,这个也即是瓶颈点。
- 2023-06-25CF765F. Souvenirs
压位trie好厉害。显然加一个数很好维护,删一个数有点不好做,考虑回滚莫队。用平衡树维护数的集合,每次插入之前用前驱/后继与插入数的差更新一下答案,可以\(O(n\sqrt{n}\logn)\),会Timelimitexceededontest7or8。看上去我们已经优化到极限了,怎么办呢?显然莫队的\(n\sqrt{
- 2023-02-04CF765F Souvenirs 题解
Preface在会压位Trie的前提下,本题最好想的做法应该是压位Trie+回滚莫队,可是竟然没人写这个做法的题解?Solution我们先转化题意:设\(a_i\)在\([l,r]\)中的前驱后继
- 2022-08-29CF765F
分块。\(f[i][j]\):\(i\)一直到第\(i\)所在块\(x\)尾端,对\(x+1\simj\)块造成贡献/\(i\)一直到\(i\)所在块\(x\)开头,对\(j\simx-1\)块造成贡献。\(mn[i][j