poj 2352 star(线段树 / 树状数组)

题意：

计算星星的等级，星星左下方的其他星星的数目就是那颗星星的等级（可以在同一水平线或竖直线上）。

 

思路：

如果用暴力的话每增加一颗星星都要跟前面所有的比一下，以确定他的等级。那将会是O(n^2)的复杂度。

这种动态得增加点，并计算总和，可以用线段树，复杂度O(logn)，每个找一下也就O(nlogn).

更新时一路上节点的w都增1，查找等级时找比a[i]小的有多少个。用数组ans统计各个等级的星星数。因为星星的坐标可能是0开始，所以建树时也要从0到所用星星中的最大坐标。

还有种更方便的方法是用树状数组，时间复杂度一样，但是空间省很多。

也是因为星星的坐标会从0开始，所以位置要全部往后挪一位。

    关于树状数组在 ：http://blog.chinaunix.net/u3/102624/showart.php?id=2058516

源程序

线段树版：
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 15000
#define M 32000
struct t
{
    int l;
    int r;
    int w;
}tree[M * 3];

void maketree(int s, int t, int n)
{
    tree[n].l = s;
    tree[n].r = t;
    tree[n].w = 0;
    if(t == s)
        return;
    int mid = (tree[n].l + tree[n].r) / 2;
    maketree(s, mid, n * 2);
    maketree(mid + 1, t, n * 2 + 1);
}
/*找在x坐标为t的星星的左下方有多少颗星星*/
int find(int s, int t, int n)
{
    if(tree[n].l == s && tree[n].r == t)
        return tree[n].w;
    else
    {
        int sum = 0;
        int mid = (tree[n].l + tree[n].r ) >> 1;
        if(s > mid )
            sum += find(s, t, n * 2 +1);
        else if(t <= mid)
            sum += find(s, t, n * 2);
        else
            sum += find(s, mid, n*2) + find(mid+1, t, n*2+1);
        return sum;
    }
}
/*更新线段树，一路上节点的w都增一*/
void insert(int x, int n)
{
    tree[n].w++;
    if(tree[n].l == tree[n].r && tree[n].r == x)
        return;
    int mid = (tree[n].l + tree[n].r ) >> 1;
    if(x <= mid)
        insert(x, n * 2);
    else insert(x, n * 2 + 1);
}

int main()
{
    int i;
    int n, max;
    int a[N], b, ans[M];

    freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    max = 0;
    for(i=0; i<n; i++)
    {
        scanf("%d%d", &a[i], &b);
        max = max < a[i] ? a[i] : max;
    }
    maketree(0, max, 1);
    memset(ans, 0, sizeof(ans));
    for(i=0; i<n; i++)
    {    
        ans[find(0, a[i], 1)]++;
        insert(a[i], 1);
    }
    for(i=0; i<n; i++)
    {
        printf("%d\n", ans[i]);
    }
    getch();
    return 0;
}
 memory： 1108   time：172

树状数组版：

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 15005
#define M 32005
int ans[M];
int n, max;

int lowbit(int n)
{
    return n & (-n);
}

void add(int index)
{
    while(index <= max+1)
    {
        ans[index]++;
        index += lowbit(index);
    }
}

int cal(int index)
{
    int sum = 0;
    while(index > 0)
    {
        sum += ans[index];
        index -= lowbit(index);
    }
    return sum;
}
int main()
{
    int i, x[N], y;
    int result[M];
    freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    max = 0;
    for(i=1; i<=n; i++)
    {
        scanf("%d%d", &x[i], &y);
        max = x[i] > max ? x[i] : max;
    }
    memset(result, 0, sizeof(result));
    for(i=1; i<=n; i++)
    {
        result[cal(x[i]+1)]++;   

        add(x[i]+1);        
    }
    for(i=0; i<n; i++)
        printf("%d\n", result[i]);
    getch();
    return 0;
}
memory： 468   time：141