안녕하세요.
일단 2010년 인터넷 I번문제는
사람 N명이주어지고
M개의 데이터 혹은 질의가 들어오는데요
데이터에는 사람의 점수가 들어오고
질의가 나오면 그때까지 누적된 특정사람의 점수의 랭킹을 출력해야 하는 문제입니다.
저는 "실시간으로 소트되는거면 힙이나 인덱스드 트리"로 되겠지 해서 생각하다가 도저히 답이 안나와서
그냥 사람들의 각 점수를 2진수화 해서 그 2진수를 그대로 2진트리로 구현했습니다.
굳이 말씀드리자면 카운터소트를 하고 싶었는데 배열을 그만큼 못잡으니
각 점수의 이진수를 왼쪽 자식 오른쪽 자식으로 해서 단말에 각 점수의 데이터의 갯수를 넣었습니다.
그러면 랭크 세는것도 트리 뎁스만에 가능할거 같더군요.
각 점수의 누적합은 10^9을 넘지않으니, 2진 트리로 해도 뎁쓰가 30을 넘지 않으니,
30 * 200000정도여서 답은 나올 거 같은데요.

1. 아래 살펴보니 인덱스드 트리나, 균형잡힌 이진트리로 풀린다는데, 어떤식으로 푸는 방법일지 궁금합니다.
2. 혹시 힙에있는(그러니까, new나 malloc으로 잡은 메모리)를 한번에 없애는 방법이 있나요. 한 테스트 데이터가 끝난후 말끔히 없애고 싶은데.. 방법을 몰라서(이런 ㅠ; 기초적인걸 몰라서 ㅠㅠ)
3. 이건.. 그냥 대회에 대한 질문인데, 보통 테스트 케이스 하나당 1초정도 제한시간인가요.? 제한시간이 딱히 적혀있지 않아서