题意：给星星的坐标，定义每个星星左下角（包括正左边和正上方）的星星数是它的level，统计各个level的星星数。
分析：乍看是个二维的统计，因为数据给出的是 y坐标升序，y相等 x坐标升序，所以可以一次读入数据，只要统计 x左边的星星数就行了，
这道题很好的启示就是二维降一维的方法————按某种规则排序。
下面给出了线段树和树状数组的写法。
点线段树cpp代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
const int root = 0;
struct Node{
int l,r,cnt;
int lnd,rnd;
}node[60005];
int cnt,cntx;
int indx[15010];
int x[15010],y[15010];
void Creat(int p,int l,int r)
{
node[p].l = l; node[p].r = r;
node[p].cnt = 0;
if (l < r)
{
int mid = (l + r) >> 1;
node[p].lnd = ++cnt;
Creat(cnt,l,mid);
node[p].rnd = ++cnt;
Creat(cnt,mid+1,r);
}
else {node[p].lnd = node[p].rnd = -1;}
}
void upData(int p)
{
if (node[p].l < node[p].r)
node[p].cnt = node[node[p].lnd].cnt + node[node[p].rnd].cnt;
}
void Insert(int p,int id)
{
if (id == node[p].l && id == node[p].r)
node[p].cnt++;
else {
int mid = (node[p].l + node[p].r) >> 1;
if (mid < id)
Insert(node[p].rnd,id);
else Insert(node[p].lnd,id);
}
upData(p);
}
int query(int p,int l,int r)
{
int ans = 0;
if (l <= node[p].l && node[p].r <= r)
ans = node[p].cnt;
else{
int mid = (node[p].l + node[p].r) >> 1;
if (mid >= l)
ans += query(node[p].lnd,l,r);
if (mid < r)
ans += query(node[p].rnd,l,r);
}
return ans;
}
int Bi_Search(int key)
{
int l = 1,r = cntx+1,mid;
while (l < r)
{
mid = (l + r) >> 1;
if (indx[mid] == key)
return mid;
else if (indx[mid] < key)
l = mid + 1;
else r = mid;
}
}
void Init_Index()
{
sort(indx+1,indx+1+cntx);
// for (int i = 1; i <= cntx; i++)
// printf("%d,",indx[i]);
int m = 1;
for (int i = 2; i <= cntx; i++)
{
if (indx[i] != indx[i-1])
{
m++;
indx[m] = indx[i];
}
}
cntx = m;
}
int main()
{
int n,i,j,k,id;
int count[15010];
while (scanf("%d",&n) != EOF)
{
for (i = 1; i <= n; i++)
{
count[i] = 0;
scanf("%d %d",&x[i],&y[i]);
indx[i] = x[i];
}
// for (i = 1; i <= n ;i++)
// printf("%d ",indx[i]);
// printf("\n");
cntx = n;
Init_Index();
/* for (i = 1; i <= cntx; i++)
printf("%d ",indx[i]);
printf("cntx = %d\n",cntx);*/
cnt = 0;
Creat(root,1,cntx);
for (i = 1; i <= n; i++)
{
id = Bi_Search(x[i]);
// printf("id = %d\n",id);
k = query(root,1,id);
// printf("i = %d,k = %d\n",i,k);
count[k] ++;
Insert(root,id);
}
for (i = 0; i < n; i++)
printf("%d\n",count[i]);
}
return 0;
}
树状数组的cpp代码：
#include<stdio.h>
int a[32002];
int level[15000];
int N;
int lowbit(int n){
return n&(-n);
}
int Sum(int n)
{
int result = 0;
while(n!=0){
result+=a[n];
n-=lowbit(n);
}
return result;
}
void Update(int n)
{
while(n<=32001){
a[n]++;
n+=lowbit(n);
}
}
void init()
{
int i;
for(i=0;i<=N;i++)
level[i]=a[i]=0;
}
int main()
{
int x,y,i;
scanf("%d",&N);
i=N;
init();
while(i--){
scanf("%d %d",&x,&y);
level[Sum(x+1)]++;
Update(x+1);
}
for(i=0;i<N;i++)
printf("%d\n",level[i]);
}