zhangxixi的博客

边分治建虚树优化：P4565暴力写挂 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135272909 https://www.luogu.com.cn/problem/P4565 首先题目的式子很难看，可以变成 ： depx+depy+dis(x,y)−deplca2(x,y)2\frac {dep_x+dep_y+dis(x,y)-dep_{lca_2(x,y)}}2 2depx​+depy​+dis(x,y)−deplca2​(x,y)​​ 然后直接边...

边分治+虚树+直径合并：P4220通道 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266426 https://www.luogu.com.cn/problem/P4220 第一棵树可以直接边分治，然后黑白染色，弄到第二棵树上建虚树 第三棵树很难搞。需要回到题目本身，发现题目没叫我们求奇奇怪怪的东西，而是求距离，肯定有啥性质，而且还是最大距离，就是一个点集的直径。 直径显然支持合并性，我们直接在虚树上树形dp进行合并即可 123456pre cod...

虚树建树（单调栈法） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266476 单调栈维护一条链，初始先按dfs序排序，考虑加入一个点 黑色为栈里面的点，红色为当前加入的点，蓝色为LCA点。 黄色部分需要全部pop掉，蓝色和红色要加入单调栈 代码见oi-wiki https://oi-wiki.org/graph/virtual-tree/

边分治、二度化 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266447 边分治可以使每次分治时恰好只有两边的点，统计贡献起来非常方便 但是朴素边分治时不行的，菊花图可以卡掉，所以要把点二度化，以这个图为例： 二度化后为： 再举个例子： 二度化后是： 绿点是原图点

动态链上第k小——整体二分+ds：P4175 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135253442 https://www.luogu.com.cn/problem/P4175 第k大先转第k小。 考虑离线。离线完后此题采用整体二分，对于当前二分区间是独立的。把所以操作的查询按时间戳排序。 对于修改操作，如果当前点上的值小于等于mid，则可以有贡献。 对于查询操作，要判断当前两点链上有多少个点有权值。可以用树上差分来解决，所以上一步的维护就要支持...

KD-tree + 二进制分组重构：P4148 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135242661 https://www.luogu.com.cn/problem/P4148 平面数点问题，空间小，可以考虑用kd-tree来解决。 只不过kd-tree是静态的，我们要支持修改，可以使用经典套路二进制分组重构。 12345pre coding at 11:19st coding at 11:43st bugging at 12:05passin...

环异或 + bitset线性基 +线段树分治 ： P3733 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135240352 https://www.luogu.com.cn/problem/P3733 包括首都的环肯定由一个生成树上一堆环并起来，也就是对于一棵生成树，我们把所有非树边对应的环丢入线性基中，然后求最大。 由于初始的图不变，所有生成树就可以不变了。 对于加边、删边、改边操作。改边相当于删+加。每条边有一个存活时间，显然线段树分治即可。 线性基...

转化为ds类 + 移轴不移图：P5324 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135237445 https://www.luogu.com.cn/problem/P5324 首先相当于一堆柱子，放倒后覆盖 [1,n][1,n][1,n] 对于平移操作，我们移起来非常麻烦，我们可以移轴不移图，移动区间 [1,n][1,n][1,n] 即可。 然而，对于一个柱子大于 nnn ，就不能拿它来覆盖，我们要动态维护，因此ds需要支持区间修改。我们维护区间m...

建图+分类讨论+dp：CF704C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135232777 https://vj.imken.moe/contest/599445#problem/C 我们直接建图，由于度数最多为2，要么是环，要么是点，要么是链。（对于操作1直接打tag即可） 对于链，我们直接 f(0/1,0/1)f(0/1,0/1)f(0/1,0/1) 表示上一位是啥，当前异或和为啥的方案数。如果是环，就破环成链，然后记一下第一个是啥。 然后就是...

括号序列匹配利器：贪心匹配 + 折线图：ARC141C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135225808 https://www.luogu.com.cn/problem/AT_arc141_c 首先可以列出一些条件，那是 sss 的必要条件： 若 pi>pi+1p_i>p_{i+1}pi​>pi+1​ ，则 si=( ,si+1=)s_i=(\,,s_{i+1}=)si​=(,si+1​=) 若 qi>qi+...