树状数组

http://poj.org/problem?id=2352
题目大意：
在坐标上有n个星星，如果某个星星坐标为(x, y), 它的左下位置为：(x0,y0)，x0<=x 且y0<=y。如果左下位置有a个星星，就表示这个星星属于level x
按照y递增，如果y相同则x递增的顺序给出n个星星，求出所有level水平的数量。

#include<cstdio>
#include<string.h>
#define maxn 32010
using namespace std;
int c[maxn],ans[maxn],n;
int lowbit(int x)
{
    return (x&(-x));
}
int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int d)//横坐标为x的星星的数量加d
{
    while(x<maxn)
    {
        c[x]+=d;
        x+=lowbit(x);
    }
}
int main()
{
    int x,y;
    memset(c,0,sizeof(c));
    memset(ans,0,sizeof(ans));
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        x++;
        ans[sum(x)]++;
        add(x,1);
    }
    for(int i=0;i<n;i++)
    {
        printf("%d\n",ans[i]);
    }
}

http://poj.org/problem?id=2481
每个奶牛有自己的一个区间，求每个奶牛的区间所覆盖的子区间个数（注意，真子集，相等的不算），按照输入的顺序输出。For each test case, output one line containing n space-separated integers, the i-th of which specifying the number of cows that are stronger than cowi

#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxn 100010
using namespace std;
int c[maxn],ans[maxn],val[maxn],n,maxv;
struct Node
{
    int x,y,id;
    bool operator <(const Node &t)const
    {
        return (y>t.y)||(y==t.y&&x<t.x);
    }
}arr[maxn];
int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=x&(-x);
    }
    return res;
}
void add(int x,int d)
{
    while(x<=maxn)
    {
        c[x]+=d;
        x+=x&(-x);
    }
}
int main()
{
  while(scanf("%d",&n)!=EOF,n)
 {
    memset(c,0,sizeof(c));
    memset(ans,0,sizeof(ans));
    memset(val,0,sizeof(ans));

    maxv=-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&arr[i].x,&arr[i].y);
        arr[i].x++;
        arr[i].y++;
        arr[i].id=i;
        maxv=max(maxv,arr[i].y);
    }
    sort(arr+1,arr+n+1);
//    for(int i=1;i<=n;i++)
//    {
//        printf("x:%d y:%d\n",arr[i].x,arr[i].y );
//    }
    for(int i=1;i<=n;i++)
    {
        if(arr[i].x==arr[i-1].x&&arr[i].y==arr[i-1].y)
            ans[arr[i].id]=ans[arr[i-1].id];
        else ans[arr[i].id]=sum(arr[i].x);

        add(arr[i].x,1);
    }
    for(int i=1;i<n;i++)
    {
        printf("%d ",ans[i]);
    }
    printf("%d\n",ans[n]);
  }

}