POJ2352樹狀數組

個人NO。1

一開始題意理解有錯。

一星星左下邊有N顆星星，那它的等級就是N。

一開始理解必須X,Y兩個坐標都小於，後來根據樣例看了一下只要左下方即可，X,Y坐標都小於等於即可，但不包括星星本身。

 
#include <iostream>   
#include <stdio.h>   
#include <string.h>   
using namespace std;  
int lowbit(int x)  
{  
    return x&-x;  
}  
int c[32005];  
int x[32005];  
int n;  
int ans[32005];  
int visit[32005];  
int a[32005];  
void add(int x,int y)//後面的所有的值得更新，不包括自身   
{  
    while(x<=32005)  
    {  
       c[x]+=y;  
       x+=lowbit(x);  
    }  
}  
int sum(int x)  
{  
    int ret=0;  
    while(x>0)  
    {  
        ret+=c[x];  
        x-=lowbit(x);  
    }  
    return ret;  
}  
int main()  
{  
    while(scanf("%d",&n)!=EOF)  
    {  
        memset(c,0,sizeof(c));  
        memset(x,0,sizeof(x));  
        memset(ans,0,sizeof(ans));  
        int x,y;  
        for(int i=1;i<=n;i++)  
        {  
            scanf("%d%d",&a[i],&y);  
            if(visit[a[i]+1]==0)  
            {  
                add(a[i]+2,1);  
                visit[a[i]+1]=1;  
            }  
            else   
            add(a[i]+1,1);//c[i]表示比i坐標小的個數   
            ans[sum(a[i]+1)]++;  
        }  
  
       for(int i=0;i<n;i++)  
           printf("%d\n",ans[i]);  
    }  
    return 0;  
}  

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int lowbit(int x)
{
    return x&-x;
}
int c[32005];
int x[32005];
int n;
int ans[32005];
int visit[32005];
int a[32005];
void add(int x,int y)//後面的所有的值得更新，不包括自身
{
    while(x<=32005)
    {
       c[x]+=y;
       x+=lowbit(x);
    }
}
int sum(int x)
{
    int ret=0;
    while(x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        memset(x,0,sizeof(x));
        memset(ans,0,sizeof(ans));
        int x,y;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i],&y);
            if(visit[a[i]+1]==0)
            {
                add(a[i]+2,1);
                visit[a[i]+1]=1;
            }
            else 
            add(a[i]+1,1);//c[i]表示比i坐標小的個數
            ans[sum(a[i]+1)]++;
        }

       for(int i=0;i<n;i++)
           printf("%d\n",ans[i]);
    }
    return 0;
}