POJ 2352 Stars【树状数组】

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目链接：POJ 2352

题目大意：在二维坐标内给定 n 个点，求出每个点的左下方（包括正下方与正左方，但是不包括自己），有多少个其他的点。

题目分析：

我们注意到，输入的点的坐标是按照 $y$ 坐标从小到大输入的，所以后输入的点一定不在先输入的星星的左下方。因此，我们想要统计当前点的左下方有多少个点，只需要统计在这个点出现之前的点，是否满足对应的要求。同时注意到，由于 $y$ 坐标已经呈现了单调递增的形式，因此我们只需要考虑 $x$ 坐标即可。

显然，在 $y$ 坐标已经是单调递增之后，想要统计有多少个点在当前点的左下方，就是在统计，有多少个点的横坐标，比当前点小。

我们使用 $loc_i$ 表示 $x$ 坐标 $i$ 处，有 $loc_i$ 个星星。那么对于当前点，如果横坐标为 $x$，显然答案就是：