20221011考试总结
20221011 考试总结
T1
假的可持久化题，弄到树上做撤销就行。
其实写可持久化 FHQ-Treap 更容易
参考 关于平衡树
还可以用块状链表搞定。
T2
树套树模板题，但是有一些不同的思考方式。
我采用了线段树套值域线段树，但是需要同时二分多个主席树，不够优雅。
值域树套位置树
一般来说，位置树套值域树更加常见，但如果有些涉及到二分的操作，也许把它们反过来会更加容易，因为反过来之后就可以在数据结构上二分，减少一个 \(\log\)。
其实位置树套值域树也可以在数据结构上二分，只是实现起来相对麻烦一些。
可以采用值域线段树套平衡树。
这个时候 FHQ-Treap 的优势就体现出来了，很简单的可以查到 \([l,r]\) 区间内数的个数。
莫队和值域分块
带修莫队可以处理单点改区间查的问题，修改一共 \(O(n^{\frac{5}{3}})\) 次，查询 \(O(n)\) 次，使用 \(O(\sqrt n)-O(1)\) 的值域分块即可处理问题。