MathTrauma

문제 링크 : https://www.acmicpc.net/problem/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 0 으로 시작하는 index 를 다루면서 개수를 따지는 문제는 언제나 헷갈린다.(언제쯤이면 실수 없이 쓸 수 있을까?) 문제에서 1 부터 N 까지의 수를 다루지만, 원형으로 배치된 상태에서 진행되는 상황은 mod 연산이 필수적이다. mod 연산에서 헷갈리지 않게 1 부터 N 까지를 0 부터 N-1 로 바꾸어 생각하자. 여기까지는 어렵지 않다. 문제는 'K 번째' 에 있다. 아래 코드에서 사용되는 qry 함수의 마지막 인자 k 는 '개수'이다. qry 는 찾고자 하는 ..

tree[node] 를 닫힌 구간 \( [l, r] \) 사이의 홀수의 개수로 정의하면 된다. #include using namespace std; int tree[440000], arr[110000]; void init(int l, int r, int node) { if(l==r) { tree[node]=arr[l]%2; return; } int mid = l+r>>1; init(l, mid, 2*node); init(mid+1, r, 2*node+1); tree[node]=tree[2*node]+tree[2*node+1]; } void upd(int l, int r, int node, int p, int v) { if(p>1; upd(l, mid, 2*node, p, v); upd(mid+1, r, ..

이 문제는 이미 persistent segment tree를 이용하여 해결한 바 있다. 코드가 짧아서 그랬는데 그 방식만 기록해 두자니 찜찜해서 오프 라인 쿼리로 해결하는 것도 적어 둔다. (당연히 오프 라인 쿼리 쪽이 압도적으로 빠르다.) 문제를 이해하기 쉬운 방식으로 재구성해보자. 어떤 학급의 학생들에게 이름순으로 일련 번호(index)를 매겼다고 가정한다. 여기서 학생들의 키(value)에 관한 정보를 얻고 싶다. 처음에 \( [l_1, r_1]\) 번 사이의 학생 중에서 키가 175cm 이 넘는 사람은 몇 명인가를 묻고 다음에 \( [l_2, r_2]\) 번에서 180cm 이상인 사람이 몇 명이지를 물었다고 하자. 이런 식으로 질문이 계속될 때, 만약 키에 관한 segment tree를 구성했다면..

닫힌 구간 [a, b] 범위 내부의 순서는 고려되지 않으므로 구간의 최소, 최대를 구해서 a, b와 비교하면 되겠다. #include using namespace std; using pii=pair; int arr[100001]; pii Tree[400005]; void upd(int l, int r, int node, int p, int v){ if(p1; upd(l, mid, 2*node, p, v), upd(mid+1, r, 2*node+1, p, v); Tree[node]= { min(Tree[2*node].first, Tree[2*node+1].first), max(Tree[2*node].second, Tree[2*node+1].second)}; } pii qry(int l, int r, int..

문제 링크 : https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 입력 순서와 값의 크기의 순서가 역전된 횟수를 '전도의 수(number of inversion)' 라고 한다. 원래 전도의 수를 세는 것이 ps에서 중요한 소재인 것인지는 잘 모르겠지만 boj에서는 많이 보게 된다. 기본적인 것으로 BOJ 1517 버블소트 를 들 수가 있겠다. 크기를 비교해서 역전된 것을 교환하는 횟수를 요구하는 시간 내에 해결하는 방법은 많다. 우선 sort ..

일차원부터 짧게 언급해 둔다. 원래 수열을 arr 이라 하자. 통상적인 구현에서 segment tree 1 번은 arr 전체를 관리하고, 2 번은 좌측 절반, 3 번은 우측 절반, ... 이런 식으로 segment tree 의 각 원소는 원래 수열의 일정 범위를 관리하는 node 라는 사실은 2 차원이던 3차원이던 변함없다. 즉, tree[2][3] 은 앞의 절반의 행에 관한 정보와 뒤의 절반에 해당되는 원래 수열의 원소들에 관한 정보를 가진다. tree[2][4] 는? 행에 관해서는 앞의 절반 그리고 열에 대해서는 첫 4분 구간에 대한 정보를 가질 것이다. 뭐 code 는 복잡해졌지만 위의 내용만 염두에 두면 번거롭기는 하지만 논리적으로 어렵지는 않다. 아래 구현에서는 i, y 가 행을 나타내고, j,..