2352.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <iostream>
#include <cstdio>

using namespace std;

const int nil = 32001;

struct node {
    int v;
    int c;
    int l,r;
}tree[32002];

int res[15000];
int nnode,Root;

int maketree(int a, int b) {
    if (a > b) return nil;
    int mid = (a+b)/2;
    int now = nnode++;
    tree[now].v = mid;
    tree[now].c = 0;
    tree[now].l = maketree(a,mid-1);
    tree[now].r = maketree(mid+1,b);
    return now;
}

int count(int root, int x) {
    if (tree[root].v == x)
        return tree[root].c - tree[tree[root].r].c;
    else if (tree[root].v < x)
        return tree[root].c - tree[tree[root].r].c + count(tree[root].r,x);
    else //tree[r].v > x
        return count(tree[root].l,x);
}

void insert(int x) {
    int p = Root;
    while (x != tree[p].v) {
        tree[p].c++;
        if (x < tree[p].v) p = tree[p].l;
        else p = tree[p].r;
        }
    tree[p].c++;
}

int main() {
    int x,y,n,i;
    
    nnode = 0;
    Root = maketree(0,32000);
    memset(res,0,sizeof(res));
    tree[nil].c = 0;
    
    scanf("%d",&n);
    for (i = 0; i < n; i++) {
        scanf("%d %d",&x,&y);
        res[count(Root,x)]++;
        insert(x);
        }

    for (i = 0; i < n; i++)
        printf("%d\n",res[i]);
    
    system("pause");
}