zhangxixi的博客

中间相遇法（分治类问题非等大分治的平衡做法） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321701 分治，如果分成两半大小不一样，很容易被卡到 O(n2)O(n^2)O(n2) 在某些题目中，利用中间相遇法，我们可以优化这个过程 其优化的前提是分治的大头在找分界点 复杂度不用证，很好理解吧 这层找地越久，下一层就越均匀

（非颜色、包含）线段类问题——离线+扫描线+DS：0926T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133309861 这种类型的题其实很单一 首先有一堆线段，有询问，直接离线，然后上扫描线，然后套DS 问题来了，ds维护什么？ 此题询问的看似是单点问题，本质是区间问题。 我们要尝试对题目进行转换，如果整个区间所有都满足，则单点必然满足 回到此题。首先扫描线满足了右端点。 那么ds只能维护左端点了。 既然是维护端点值，那么只能维护最值。 维护最值...

坐标系上的交互+分治与交互：CF788D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133281428 https://codeforces.com/contest/788/problem/D 坐标系上的交互有一种常见套路，就是抓住一些关键的线 x轴y轴 y=x（就是此题） 然后考虑接下来怎么做。 交互题常见有二分的套路，此题我们可以考虑推广到分治。 不断判断mid，然后就可以求出最近的范围，并递归下去即可 1234567891011121...

和直径相关的性质：CF842E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133280849 https://codeforces.com/contest/842/problem/E 关键性质：多条直径点的交集必然非空且一定为连续一段 也就是说： 必然可以划分成两个集合，使得两个集合各选一个点上的路径必然为一条直径 然后对于此题求端点，我们就可以维护两个集合，然后就行了 至于这题有什么启发，我现在还没想懂 123456789101112131415161...

生成函数套sperner定理+哈夫曼树思想维护多个多项式乘法：CF1257G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133270189 首先有spener定理，肯定选 m2\frac m 22m​ 最优 那怎么计算本质不同的选数方案呢？根据一些生成函数的知识，某个质数出现次数为 ccc ，我们就可以令其为 1+x+x2+⋯+xc1+x+x^2+\dots+x^c1+x+x2+⋯+xc ，然后所有多项式相乘的第 m2\frac m 22m​ 项即为答案...

值域范围内和倍数有关的一种分组方法+分组问题处理出上下界+通过调和级数按顺序枚举因倍数：ARC141D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133248890 2m2m2m 个数分成 mmm 组，一种合法方案必然是 m+1∼2Mm+1\sim 2Mm+1∼2M 所以考虑对每个数进行分组 Trick1 值域范围内和倍数有关的一种分组方法 思考方法：每个数 x=k2ix=k2^ix=k2i ，放在第 kkk 组里 直观理解：每个奇数不断翻倍在一个组内 ...

可删除背包（计数类）=＞转移数组进行展开：ABC321F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133219375 https://atcoder.jp/contests/abc321/tasks/abc321_f 还真没见过这个套路，呜呜┭┮﹏┭┮ 首先加就正常加，从后往前 但删的话应该是从前往后减 为什么呢？ 先写一下自己的理解，加要从后往前加是为了防止加多次 减的话为了保证每个被删的数只减一次，应该从前往后。 考虑前 iii 个已经被还原了，那...

交错序列——差分：GZOI2023D2T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133247058 单点修改，全局查询交错序列最大值（ max⁡(∑i(−1)ibi)\max(\sum_i (-1)^ib_i)max(∑i​(−1)ibi​) ）， bbb 为 aaa 的子序列 正常做法是线段树，但对于交错序列问题，有一种更好的方法，就是差分 考虑 ai−aja_i-a_jai​−aj​ ，本质就是 [j+1,i][j+1,i][j+1,i] ...

具有部分单调性的区间个数计数问题——考虑分治：GZOI2023Day1T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133218885 询问有多少区间满足 Sum×Len≤Max2Sum\times Len\le Max^2Sum×Len≤Max2 发现在 MaxMaxMax 定的情况下，显然满足单调性 对于此类题目，可以考虑分治处理 对于当前分治区间，我们采用的分治策略是左右独立算+计算跨区间 显然必然是一段后缀加一段前缀。 先枚举左端点，然后根据上...

点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp：0922T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133217931 首先连通块，所以点分治肯定是 Trick1 钦定选根的连通块dp 对于钦定选根的连通块dp，有一种常见思路 先对原树求其dfn序，按dfn序 倒序 求解 具体的，对于当前点 iii （注意这里都是指dfn序），我们可以钦定 iii 是否选 如果 iii 选，就由 i+1i+1i+1 ，也就是 iii 的第一个儿子转移过来...