링크: https://www.acmicpc.net/problem/9034오랜만의 포스팅. 아마 한동안 문제를 풀 시간은 없을 듯.. ㅠ문제매번 \(i\)번 선수에게 더해지는 점수가 주어지고, \(x\)번째 선수가 몇 등인지 실시간으로 출력하는 문제이다. 먼저 어떤 선수의 등수는 "그 선수보다 점수가 더 높은 사람의 수 + 1"이다.매번 탐색을 하거나, 정렬을 한다면 \(100,000\)명의 선수에 대한 \(200,000\)번의 질의에 대답하기엔 시간상으로 버겁다. 내 등수는 구간 [내 점수 + 1, ∞)에 있는 사람의 수 + 1과 같다. 점수의 합은 최대 \(10^{9}\)이므로, 모든 점수를 압축할 필요가 있다. 이건 좌표압축 문제(BOJ 18870 - 좌표 압축)를 먼저 풀어보기를 권장한다.점수가 더..

링크: https://www.acmicpc.net/problem/2517문제최선의 등수는 다시 말하면, "a[k] = 어떤 k 입장에서 왼쪽으로 자신보다 높은 실력의 개수" 이다."왼쪽으로"의 뜻은 "이전까지 등장한"과 같은 말이고, 자신보다 높은 실력의 개수는 기록을 통해서 셀 수 있다.문제는 수의 범위가 1,000,000,000 이하라서 수를 직접 저장하기는 힘들어 보인다.문제 조건 중, 참가한 선수들의 실력은 모두 다르다는 조건이 있다. 그럼 같은 의미로 그 사람의 등수를 기록하자.N은 50만 이하이므로, 등장한 등수(rank)를 1로 기록하고 k 위치에서 자신보다 높은 실력(=등수)는 세그먼트 트리로 쉽게 셀 수 있다.선수 k의 최선의 등수는 query(자신의 등수 + 1, 범위 끝) + 1이다...

세그먼트 트리는 임의의 위치의 값들이 계속 변화하고, 특정 구간에 대한 연산(어떤 구간의 합, 어떤 구간 중 최소값 등)을 빠르게 구할 때 용이한 자료구조이다.한국어로는 구간 합 트리?라고도 하는 것 같다. 이 글을 적는 이유는 세그먼트 트리 자체를 다루기 위한 것은 아니고, 크기를 2배로 잡는 대신에 비재귀 형태로 간단하게 작성할 수 있는 코드를 소개하려고 한다.처음 접한 건 2016년 쯤 코드포스에서 읽었다. 워낙 간단하고 명료해서 아직까지 외우고 있다.링크: http://codeforces.com/blog/entry/18051대회에서도 자주 사용했는데, 블로그 포스팅은 한 적이 없어서 나중을 위해 다시 적어둔다. 자세한 설명은 원문 링크에 자세히 나와있으므로 생략한다.사용할 때 주의할 점은, que..