平常改的题里面那些还算有意思的题

记录一些印象还不错的题。 **[dy0607]revive** **[ShichengXiao]Xor** **[Simu]test** **[Wearry]strange** ### $[Simu]babystep$ 题意：给定一个$n\times n$的网格图，一开始断掉一条边并查询两点是否在一个连通块内，之后给定$m-1$个询问$(x,y,z,o,x',y',z',o')$，上次询问的答案为是，那么断掉前四个所代表的一条边（给的是横纵坐标），否则断掉后四个所代表的边，并继续询问。$n\le 500,m\le 2n^2-2n$ 这题很妙。 你可以把一个点变成一个正方形格子，于是断边变成了连接两个方格边上的点。就像这样： $\begin{matrix}1\ 2\ 3\\ 4\ 5\ 6\end{matrix}$$ 1号点拆成$1,2,4,5$，2号点拆成$2,3,5,6$。然后断边就把$2,5$这两个点连接起来。 一开始这个转化后的大格子的边缘是连起来的，然后我们每次可以用$dsu$实现这个操作。但当我们合并前就发现原来两个点就连通的时候，实际上原图上的两点就断开了。就这样在$merge$的时候判断一下就行了。这个可以在原图上画一画。 ### $2019.3.23[dy0607]lemon$ 这里写的是$zhou888$的解法。 我们考虑一个比较显然的贪心，就是记录一下每个点的到根的前缀$\min$，然后排序之后把$a$也排序贪心选。 但是当我们遇到不能选的时候，显然我们就要加坚固度了。但实际上我们对于所有没选的点都要枚举一下，然后再继续贪心验证，否则正确性显然是错的，因为每个点的限制会受到影响（因为是前缀$\min$）。这样时间复杂度是$O(n^2\log n)$的。 我们考虑把它直接放到序列上，然后