数点
泛化ψ(｀∇´)ψ
这种问题一般都是，有一些不同种类的限制，比如值域限制和下标限制。
你需要对满足两种条件的点/元素计数。
一个比较经典的套路是，对于二维数点，考虑枚举下标，用树状数组维护值域，问题可以转化为一个所谓动态的前缀和，思想有点类似可持久化。
如果都是下标，比如例题第一题，也是一个道理。
有的 dp 里面也会遇到类似的问题，比如 The Battle Of Chibi 那题。
这类问题的本质是，考虑将多种限制分离开来，方便计算，因为显然分开满足严格弱于同时满足吧（
这类问题好像还可以 cdq，三维及以上就需要了，但是我现在没有学的必要，先咕着。
例题ψ(｀∇´)ψ
P2163 [SHOI2007]园丁的烦恼ψ(｀∇´)ψ
看来一般的难题是难不倒这位园丁的，国王最后打算用车轮战来消耗他的实力： “年轻人，在我的花园里有 \(n\) 棵树，每一棵树可以用一个整数坐标来表示，一会儿，我的 \(m\) 个骑士们会来轮番询问你某一个矩阵内有多少树，如果你不能立即答对，你就准备走人吧！”说完，国王气呼呼地先走了。
这下轮到园丁傻眼了，他没有准备过这样的问题。所幸的是，作为“全国园丁保护联盟”的会长——你，可以成为他的最后一根救命稻草。
数据范围 5e5，值域 1e7。
这个就是板子二维数点吧感觉，就直接枚举 \(x\)，用树状数组维护 \(y\)。
问题本质上可以分开转化为两个维度上的前缀和，但是二维前缀和寄了，空间开不下，直接二维树状数组也寄了。
所以你考虑枚举一个维度，另外一个维度用树状数组维护。
其实感觉这个题板子的样子不是很像，应该看下面两个题。
Code
1 | |
ABC283F - Permutation Distanceψ(｀∇´)ψ
这题要考虑拆一下，分开来算。
20230111C - Aψ(｀∇´)ψ
这题有额外的限制，可以通过其他方式解决。
最后更新:
October 13, 2023