拿这个题研究了好几天的树状数组和线段树

题意是给一些星星的x,y坐标,星星的层数为不在其上和其右的星星的个数.

因为星星是先按y的升序再按x的升序给出的,所以之后的星星不会影响前面的星星的层次,用树状数组统计小于等于当前星星x坐标的星星个数即为level.

树状数组的做法是,每读入一组坐标,先算出其level,再更新数组.最后输出的是各level星星数.注意树状数组是从1开始的所以x要+1.数组也不要开小.

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define maxX 32003
#define lowbit(i) ((i)&(-i))
int level[15001];
int tree[maxX];
int n;

void update(int i,int val)
{
    while(i<=maxX)
    {
        tree[i]+=val;
        i+=lowbit(i);
    }
}
int sum(int i)
{
    int s=0;
    while(i>0)
    {
        s+=tree[i];
        i-=lowbit(i);
    }
    return s;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x,y; scanf("%d%d",&x,&y);
        ++x;
        ++level[sum(x)];
        update(x,1);
    }
    for(int i=0;i<n;i++)
        printf("%d\n",level[i]);
}

线段树的做法是,每插入一颗星星(设其横坐标为x),将区间[x,32000]加1,即后面的星星的层数加1,这样后面的星星调用query(x`)便可返回层数.

#include <cstdio>
struct node
{
    int l,r,val;
} tree[32000*4];

void create(int l,int r,int root)
{
    tree[root].l=l;tree[root].r=r;
    tree[root].val=0;
    if(l==r) return;
    int m=(l+r)/2;
    create(l,m,root*2);
    create(m+1,r,root*2+1);
}

void update(int l,int r,int root,int val)
{
    if(tree[root].l==l && tree[root].r==r)
    {
        tree[root].val+=val;
        return;
    }
    int m=(tree[root].l+tree[root].r)/2;
    if(r<=m) update(l,r,root*2,val);
    else if(l>m) update(l,r,root*2+1,val);
    else
    {
        update(l,m,root*2,val);
        update(m+1,r,root*2+1,val);
    }
}
int query(int x,int root)
{
    if(tree[root].l==tree[root].r)
        return tree[root].val;
    int m=(tree[root].l+tree[root].r)/2;
    if(x<=m) return query(x,root*2)+tree[root].val;
    else return query(x,root*2+1)+tree[root].val;
}
int level[32001];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,n,x,y;
    scanf("%d",&n);
    create(0,32000,1);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ++level[query(x,1)];
        update(x,32000,1,1);
    }
    for(i=0;i<n;i++)
        printf("%d\n",level[i]);
}