数星星发表时间:2022-10-27 20:40 数星星 问题描述 小粽今晚在数星星。 小粽把整个天空看作一个平面,她测出了她看见的每个星星的坐标,第 ii 颗星星的坐标为 (xi,yi)(xi,yi)。 光数星星实在是太无聊了,小粽想知道,对于每颗星星,其左下方的星星的数量,即对于每个 ii,小粽想要知道满足 j≠ij≠i,且 xj≤xi,yj≤yixj≤xi,yj≤yi 的 jj 的数量。 输入格式 第一行一个正整数 nn,表示星星的数量。 接下来 nn 行,每行两个正整数 xi,yixi,yi,表示第 ii 颗星星的坐标。 输格式 输出共 nn 行,每行输出一个正整数,表示第 ii 颗星星左下方星星的数量。 输入样例 1 5 11 51 71 33 55 输样例 1 样例 2 点此下载。 数据规模及约定 对于 30%30% 的数据有 n≤500n≤500; 对于 60%60% 的数据有 n≤8000n≤8000; 对于 100%100% 的数据有 n≤3×105n≤3×105,所有坐标都在 int 范围内,不存在两个不同的点有相同的坐标。 提示 [回想一下归并求逆序对咋做的?你就会做这个题辣] [有兴趣的同学百度二维偏序~] 代码 #include <cstdio> #include <algorithm> #pragma warning(disable:4996); #define maxn 500000
using namespace std;
struct Point { int x, y, id;
void read(int id) { this->id = id; scanf("%d%d", &x, &y); }
// 先比较x轴,再比较y轴 bool operator < (const Point &a) const { return x == a.x ? y < a.y : x < a.x; } };
// a: 原数组 // b: 归并辅助数组 Point a[maxn + 10], b[maxn + 10];
// ans: ans[i] 表示第 i 个点左下方的点的数目int ans[maxn + 10];
/* ========== 代码实现开始 ========= */
void solve(int l, int r) { if (l >= r) return;
int m = l + r >> 1;
solve(l, m); solve(m + 1, r);//分治,解决子问题
//归并过程 int t1 = l, t2 = m + 1, t = l; while (t1 <= m && t2 <= r){ if (a[t1].y <= a[t2].y) {//归并 b[t++] = a[t1++]; } else { ans[a[t2].id] += t1 - l;//除了正常的归并外,还需统计左侧对右侧的贡献 b[t++] = a[t2++]; } } for (int i = t1; i <= m; i++) { b[t++] = a[t1++]; } for (int i = t2; i <= r; i++) { ans[a[t2].id] += t1 - l;//除了正常的归并外,还需统计左侧对右侧的贡献 b[t++] = a[t2++]; }
for (int i = l; i <= r; i++) a[i] = b[i]; }
// solve 被调用后,ans 数组应被计算好void solve(int n) { sort(a, a + n); for (int i = 0; i < n; i++) ans[i] = 0;
solve(0, n - 1); }
/* ========== 代码实现结束 ========= */
int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) a[i].read(i);
solve(n);
for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
return 0; |