zhangxixi的博客

zkw线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132177887 启蒙题： http://zhengruioi.com/problem/2609 参考论文： https://wenku.baidu.com/view/f27db60ee87101f69e319544.html?wkts=1691491614153 不用递归，通过位运算实现的线段树。（本质：线段树为一颗满二叉树） 如果值域为 VVV ，那么zkw只能维护到 V−2V-2V−2 的值...

质因数分解上的势能分析：AGC003D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132153999 https://www.luogu.com.cn/problem/AT_agc003_d 题目问是否存在立方，值域范围 1e101e101e10 ，所以很明显类似根号类的题，进行 3^3\sqrt{}3​ 分解个质因数。 二分图点对的性质很明显，但很容易忽略它在接下来分析中的作用。 此时剩下最多剩下2个质数，其实分类讨论一下即可。 对于 p×qp\tim...

线段树合并思想 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135188 直接维护很大，所以每个节点动态开点。 合并时按顺序，一个有一个没直接把有那个连上去。 否则递归。

cqd分治思想 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135114 https://www.luogu.com.cn/problem/P3810 常用于维护三维偏序问题，对于相等的情况处理我感觉不太好，之前ABC打cdq被制裁了 三维，第一维显然排序 分治，所以第二维很明显了。因为只需要考虑左对右的贡献，所以黑白染色一下，再按b排即可。然后黑白一个对应查询一个对应修改操作。 最后一个拿树状数组

扫描线思想 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135063 https://www.luogu.com.cn/problem/P5490 本质就是把每个矩形拆成上边和下边，下边为加，上边为减（从下往上枚举） 变成处理一维上的线段长度并，拿个线段树维护 最好拿点离散化一下，动态开点容易被制裁

四边形不等式优化 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132134968 例题： https://www.luogu.com.cn/problem/P4767 用于优化前 iii 个放 jjj 个的dp，优化的是决策点的决策范围（即转移的 kkk ） 设转移点为 op(i,j)op(i,j)op(i,j) op(i,j)op(i,j)op(i,j) 在A， op(i,j−1)op(i,j-1)op(i,j−1) 在B，感性理解A枚举显然在B之后 ...

兔队线段树：楼房重建 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126096 https://www.luogu.com.cn/problem/P4198 本质：在线段树上每个节点维护信息时再深入到底部，加个 log⁡\loglog O(nlog⁡2n)O(n\log^2n)O(nlog2n) 总比 O(n2)O(n^2)O(n2) 优。 抽象到本题，就是对于每个线段树节点单独维护只考虑这个区间的答案。 合并的过程，显然左子树可以直接继承，所以可以...

线段树分治 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126153 https://www.luogu.com.cn/problem/P5787 理解： 操作离线 用时间线段树维护 整体统计答案，进入到某个节点加入，离开时撤销 可以用可撤销数据结构维护（可能可以可持久化或LCT维护？以后再学）

分类讨论+反悔贪心来实现模拟费用流：[NOI2019] 序列 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132112120 https://www.luogu.com.cn/problem/P5470 很容易把费用流建出来。 然后要模拟这个过程，把核心要点，也就是 K−LK-LK−L 这个限制提取出来。 因为在此限制下答案不劣，所以优先枚举这个限制下的答案。 模拟费用流，所以必然有反悔贪心，分类讨论一下。 总结下来，对于模拟费用流的方法： 分类讨论...

对于模拟最大流的一些猜测 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093553 先把最大流转成最小割。 然后对最小割分类讨论，观察性质，看看有什么不用跑最大流的做法？ 等我长大再回来想。