算法竞赛

第二分块，神仙大分块题，不过想清楚了后应该难度相对不太大。 Part.1 先看这题的数据范围（公式），想到分块的方式应该与值域有关。另外我们可以发现，我们的值是只减小不增大的，考虑值域上应该有一个均摊，对每块做 …

线段树分治模板题。 Part.1 Q：如果没有修改，我们怎么做？ A：用并查集维护连通性。 直接扫一遍，我们加进来一个数，就先令答案++，看一下四个方向，如果某个方向与当前点不在同一个连通块中，那么就合并并查集 …

模拟退火 退火大法吼啊！ 首先不知道模拟退火的请左转这个题 然后回到我们的这个问题，实际上我们的这个题是图论中的一类经典问题——最大团问题，这个问题是指在一个图中找一个子图是完全图，使这个子图的点数最多。这是一 …

莫队二次离线 最近学了这个黑科技，来写篇题解分享一下。 顺便（公式） Part.1 问题引入 有一个序列，每次查询一个区间中有几个二元组的的异或值在二进制下有（公式）个（公式）。 考虑莫队。 先用莫队转化问题， …

其实本蒟蒻自己想了一会后便有了一些思路，但实现方面还是还是学习了（公式）的做法的 强制在线导致一些离线做法没有办法解决（如莫队），我们考虑分块，预处理出第l到第r个块的众数次数，再把零散块的数一个一个更新答案。 …

如果你其他（公式）还没有刷完建议不要来刷这道题，因为： 实际上，这是一道正宗的计算几何题。 Part.1 没什么好说的，既然都知道这是一道计算几何题，请先自行学习计算几何的基础知识。 你需要掌握的有：向量的加， …

​ 看完题目我们都知道是平衡树，而且是要资瓷区间操作的平衡树，并且要能区间翻转，所以我们被迫选择自带三倍大常数的（公式），剩下的都是一些平衡树的基操了。 操作（公式） ：插入，很简单。该怎么插就怎么插 操作（公 …

一道卡常好题。 我们考虑暴力做法，我们就可以直接对每个点维护相邻的点的平衡树，修改就暴力修改，查询就直接查询就可以了。 显然不对 那么我们怎么优化这个算法呢？ 我们可以先进行树链剖分，然后每个点只维护她的轻儿子 …

线段树入门题。 题意很清晰，通过观察屑的定义，可以发现先辈有如下性质： ​ 对于长度为（公式）序列（公式），如果它是先辈，那么它满足： ​ （公式） 为什么呢？通过观察，我们发现先辈的后缀中除了它自己外，它的最 …

场外选手来水波题解。 Part.1 先考虑询问怎么做。 首先我们考虑异或有一个很好的性质，可差分性。 考虑对序列做一个前缀异或和，一段区间（公式）的异或和为（公式）,实际上就是（公式）。所以现在我们只用查询序列 …