标签：ABC136F 一个点 包含 cdot 贡献 象限 Points Enclosed 计算

前言

模拟赛 \(\rm{T1}\) , 全世界都切出来了

思路

首先容易想到换贡献主体, 容易想到按点计算贡献 (所以我赛时为什么叉掉这个直接去按矩阵算贡献了, 无语)

考虑对于一个点, 其贡献的来源:
只要有一个子集构成的矩形包含它, 就会产生贡献

问题转化为对于一个点, 有多少个子集包含它

考虑包含的性质
发现对于这样一个点

只要 \(1, 3\) 象限和 \(2, 4\) 象限同时出现过点或者出现过这个点即可

容易用二维数点统计出 \(1, 2, 3, 4\) 象限的点的个数 (当然乱搞的话随便怎么搞)

令 \(p_1, p_2, p_3, p_4\) 分别表示 \(4\) 个象限中点的个数, 考虑计算答案
如果直接按照上面的计算, 答案为

\[2^{n - 1} + (2^{p_1} - 1)(2^{p_3} - 1) \cdot 2^{p_2}2^{p_4} + (2^{p_2} - 1)(2^{p_4} - 1) \cdot 2^{p_1}2^{p_3} \]

发现这样子计算会算重, 考虑去重
容易发现 \((2^{p_1} - 1)(2^{p_3} - 1) \cdot 2^{p_2}2^{p_4}\) 和 \((2^{p_2} - 1)(2^{p_4} - 1) \cdot 2^{p_1}2^{p_3}\) 算重了 \((2^{p_1} - 1)(2^{p_3} - 1)(2^{p_2} - 1)(2^{p_4} - 1)\) 种情况, 减去即可

总结

一类贡献主体的变化问题
一般来说需要计算被包含和自己拓张两种情况

善于按照数量级判断什么思路更正确

不管怎么样, 每日一练和 \(\rm{whk}\) 必须继续

标签：ABC136F,一个点,包含,cdot,贡献,象限,Points,Enclosed,计算
From： https://www.cnblogs.com/YzaCsp/p/18670908