POJ 2352 Stars
题目大意: 有n个星星, 现在分别给出它们的坐标(按y递增的顺序给出),每个星星有一个等级(该星星的等级是x坐标和y坐标都不大于该星的星星数),先要求出每个等级的星星有多少个
思路:用线段树或树状数组, 由于是按y递增的坐标给出的, 新加入一个点只需判断区间【1,x】多少个点, 并更新后面包含他区间的点的个数
Ps:第一道树状数组, 资料链接资料1 资料2,顺便线段树练练手
code:树状数组
#include <stdio.h>
int n = 0, c[32002];
int lowbit(int x)
{
return x&(-x);
}
void add (int x)
{
while(x<=32002)
{
c[x]++;
x += lowbit(x);
}
}
int sum(int x)
{
int s = 0;
while(x>0)
{
s += c[x];
x -= lowbit(x);
}
return s;
}
int main()
{
int i = 0, x = 0, y = 0, level[15002];
while(scanf("%d",&n) != EOF)
{
memset(level, 0, sizeof(level));
memset(c, 0, sizeof(level));
for(i = 0; i<n; i++)
{
scanf("%d %d", &x, &y);
x++;//从1开始
level[sum(x)]++;
add(x);
}
for(i = 0; i<n; i++)
printf("%d\n",level[i]);
}
return 0;
}
code:线段树
#include <stdio.h>
#include <string.h>
#define max 32002
struct
{
int sum, l, r;
}tree[4*max];
void build_tree(int l, int r, int p)
{
int m = (l+r)/2;
tree[p].sum = 0;
if(l == r)
{
tree[p].l = tree[p].r = l;
return ;
}
tree[p].l = l; tree[p].r = r;
build_tree(l, m, p*2);
build_tree(m+1, r, p*2+1);
}
void add(int l, int r, int p)
{
int m = (tree[p].l+tree[p].r)/2;
if(tree[p].l == l && tree[p].r == r)
{
tree[p].sum++;
return ;
}
if(l>m)
add(l, r, 2*p+1);
else if(r<=m)
add(l, r, 2*p);
else
{
add(l, m, 2*p);
add(m+1, r, 2*p+1);
}
tree[p].sum = tree[p*2].sum+tree[p*2+1].sum;
}
int query(int l, int r, int p)
{
int m = (tree[p].l+tree[p].r)/2;
if(tree[p].l == l && tree[p].r == r)
return tree[p].sum;
if(l>m)
return query(l, r, 2*p+1);
else if(r<=m)
return query(l, r, 2*p);
else
return query(l, m, 2*p)+query(m+1, r, 2*p+1);
}
int main()
{
int i = 0, n = 0, x= 0, y = 0, lev[15002];
while(scanf("%d", &n) != EOF)
{
memset(lev, 0, sizeof(lev));
build_tree(0, max, 1);
for(i = 0; i<n; i++)
{
scanf("%d %d", &x, &y);
lev[query(0, x, 1)]++;
add(x, x, 1);
}
for(i = 0; i<n; i++)
printf("%d\n", lev[i]);
}
return 0;
}
作者:ulquiorra0cifer
补充:软件开发 , C++ ,