题目大意
对于二维平面上的n个点，给出点的坐标。定义一个点A覆盖的点的个数为满足以下条件的点B的个数：点B的x <= 点A的x坐标，点B的y坐标 <= 点A的y坐标。
给出N个点的坐标，求出覆盖点的个数分别为0, 1, ... N-1 的点各有多少个。
题目分析
对于二维平面的点问题，可以考虑先进行行列排序，然后进行处理。对点进行排序（y从小到大，y相同，x从小到大）之后，按照y从小到大进行：单独考虑一行的点的x坐标，此时x坐标是升序的，因此当前点的肯定可以覆盖当前行中的之前访问的点；对于下方的点，它们的y坐标肯定小于当前点的y坐标，因此只考虑点的x坐标，如果x坐标小于等于当前点的x坐标，则点被当前点覆盖。
于是问题就化为了，按照从左下到右上的顺序遍历每个点的时候，比较该点和之前访问过的点的x坐标，统计之前点中x坐标小于等于当前点x坐标的个数。
这就成了一个查找问题，查找问题可以考虑使用二查找树，于是可以使用treap这种平衡树。
实现(c++)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAX_NODE_NUM 15500
struct TreapNode{
int key;
int priority;
int size;
int count;
TreapNode* child[2];
TreapNode(int val){
key = val;
child[0] = child[1] = NULL;
size = count = 1;
priority = rand();
}
void Update(){
size = count;
if (child[0]){
size += child[0]->size;
}
if (child[1]){
size += child[1]->size;
}
}
}; struct Treap{
TreapNode* root;
Treap() :root(NULL){}; void Rotate(TreapNode*& node, int dir){
TreapNode* ch = node->child[dir];
node->child[dir] = ch->child[!dir];
ch->child[!dir] = node; node->Update(); //这时候node已经旋转到下方一层，因此size可能发生变化 node = ch;
} void Insert(TreapNode*& node, int key){
if (!node){
node = new TreapNode(key);
}
else if (node->key == key){
node->count++;
}
else {
int dir = node->key < key;
Insert(node->child[dir], key);
if (node->priority < node->child[dir]->priority){
Rotate(node, dir);
}
}
node->Update();
}
void debug(TreapNode* node){
if (node){
debug(node->child[0]);
printf("node's key = %d, priority = %d, count = %d, size = %d\n", node->key, node->priority, node->count, node->size);
debug(node->child[1]);
}
} int GetLessK(TreapNode* node, int k){
int sum = 0;
if (!node){
return 0;
}
if (node->key > k){
sum += GetLessK(node->child[0], k);
}
else{
sum += node->count;
if (node->child[0]){
sum += node->child[0]->size;
}
sum += GetLessK(node->child[1], k);
}
return sum;
}
}; struct Point{
int x;
int y;
}; Point gPoints[MAX_NODE_NUM]; Treap gTreap;
int gCoverNum[MAX_NODE_NUM];
int main(){ int N;
scanf("%d", &N);
for (int i = 0; i < N; i++){
scanf("%d %d", &gPoints[i].x, &gPoints[i].y);
gCoverNum[i] = 0;
}
for (int i = 0; i < N; i++){
int less_count = gTreap.GetLessK(gTreap.root, gPoints[i].x);
gCoverNum[less_count] ++; gTreap.Insert(gTreap.root, gPoints[i].x); /*rintf("##################\n");
gTreap.debug(gTreap.root);
printf("##################\n");
*/ }
for (int i = 0; i < N; i++){
printf("%d\n", gCoverNum[i]);
}
return 0;
}