AcWing 1265. 数星星（二维偏序问题+树状数组）

题目链接

https://www.acwing.com/problem/content/description/1267/

思路

二位偏序问题，我们已经直到了这个坐标轴是按照先 y 升序再按照 x 升序来输入的，那么对于这道题来说，因为已经确保了所有可能小于当前点的点都在当前点前面出现，我们只需要使用树状数组不断动态求前缀和即可。树状数组的下标需要从1开始，所以在处理的时候还要稍微注意一下（加一操作即可）。

那么我们求解的这个前缀和就是x轴小于等于当前的 loc_x 的星星数量（不包含当前这个星星）

代码

#include
#include
#include
using namespace std;

#define ll long long

const int N = 2e5+10;

ll n,m,ans[N];

pair a[N];


struct BinaryTree{
	ll tree[Na[i].second>>a[i].first;
		sort(a+1,a+1+n);
	}
	
	
}BT;

int main()
{
	BT.build();
	for(int i = 1;i