Hdu-2353 Stars

[제목 링크]
4. 567914. 나무 모양 의 배열 을 보 자마자 이 문 제 는 2 차원 유지 가 필요 하 다 고 생각 했 습 니 다. 댓 글 구역 의 큰 사람 이 알려 주 는 것 을 보면 알 수 있 습 니 다.
#include
#include
#include
#include
using namespace std;
const int Max_n=1e5+10;

int n;
int c[Max_n],k[Max_n];

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

void update(int k,int val){
    while(k1;
        k+=lowbit(k);
    }
}

int query(int k){
    int ans=0;
    while(k>0){
        ans+=c[k];
        k-=lowbit(k);
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    int x,y;
    memset(c,0,sizeof(c));
    memset(k,0,sizeof(k));
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        x++; //x=0  update      
        k[query(x)]++;
        update(x,1);
    }
    for(int i=0;iprintf("%d
"
,k[i]); return 0; }

좋은 웹페이지 즐겨찾기