MathTrauma

문제 링크 : https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 최대 최소 세그먼트 트리를 Bottom-Up 방식으로 구현해 보자. 이 경우에 이미 결과를 알고 있는 토너먼트 대진표를 보면 쉽게 이해가 된다. LOL, NBA 혹은 바둑 뭐든 상관없다. Rating 이 높은 쪽이 항상 이긴다고 가정하자. 우승한 팀부터 차례로 값를 줄여가며 각 팀에 rating을 부여하면 최대 세그먼트 트리가 된다. 혹은 랭킹을..

문제 링크 : https://www.acmicpc.net/problem/22876 22876번: 츠바메가에시 "츠바메가에시"(つばめがえし)는 일본의 검사 "사사키 코지로"가 날아가는 제비를 베었다고 전해지는 검 초식의 이름이다. 기록상으로는 세 번 연속 칼질을 했다고 전해지나, 실제로 기술을 재 www.acmicpc.net 어릴 적 게임에서 보았던 이름을 보게 되어 반가운 마음으로 문제를 읽었는데... 후회했다. 매 번 세그먼트 트리를 설명할 수 없으니 세그먼트 트리에 대한 설명은 여기 를 참조하자. 일단 예외적인 경우부터, 행이나 열이 3 개 이하이면 모두 제거할 수 있으니 답은 전체 제비의 합이다. 위의 경우가 아니라면, 1 행을 제거하면 모든 열(수십만 개일 수 있는)에 합에 영향을 미치고(upda..

문제 링크 : https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 보고 싶은 DVD 를 빼내서 가장 앞으로 가져다 놓는 작업을 한 번 하는 동안, 그 DVD 위에 있던 다른 것들은 자신 위에 쌓여 있던 개수가 모두 1 늘게 된다. 구간에 대해 update가 필요한 상황이니 세그먼트 트리나 펜윅 트리를 쓰고 싶은 생각이 들었다. 다만, 빼낸 DVD 를 옮겨 놓기 때문에 약간의 트릭이 필요했다. 쌓는다고 생각하지 말고 왼쪽부터 차례로 번호를 붙..

문제 링크 : https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net Lazy Propagation 연습 문제인가? 더 효율적인 방법이 있을 것 같은데... 여기 있는 코드는 흔히 사용되는 코드들과 약간 다를 것인데, 관련된 설명은 다음 글에 있다. 2022.09.04 - [BOJ/Segment Tree] - BOJ 10999 구간합 구하기 2 - 두 가지 구현 BOJ 10999 구간합 구하기 2 - 두 가지 구..

문제링크 : [https://www.acmicpc.net/problem/7626] 7626번: 직사각형 첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 www.acmicpc.net 좌표 압축(coordinates compression)과 스위핑(sweeping) 두 주제 자체에 대해서는 검색으로 잘 정리된 글들을 많이 찾을 수 있었다. 그래서 따로 설명을 보태지는 않는다. 다만 인덱싱(indexing)에 대해서는 하나 집고 넘어간다. 여기서는 좌표가 아닌 구간을 인덱싱하고 이를 세그먼트 트리로 관리한다. 세그먼..

Range update 를 해야 하기 때문에 소위 Lazy Propagation 을 구현해야 하는데... 두 가지 다른 구현을 가지고 비교해 보기 위해 글을 쓴다. 두 구현의 우열을 논하는 것은 아니다. 이해하기 편한 쪽을 선택하면 되겠다. 구간 업데이트가 \( O(\log(n))\) 으로 동작하려면 어떻게 되어야 하는가? (1) node 의 관리 구간이 업데이트 구간에 포함되면 더 이상 하위 노드로 재귀 호출을 해서는 안된다. (2) 도달한 노드의 대표값은 업데이트 되어야만 한다.(그래야 상위 노드의 값도 제대로 된 값을 가지게 된다.) 위의 두 사항을 염두에 두고 있자. 1. 널리 쓰이는 구현 이제 흔히 보이는 lazy propagation 구현 코드부터 보자. 먼저 range update 를 수행하..

max 를 찾는 문제의 작은 변형. tree 의 각 노드를 pair로 두고 으뜸값과 버금값을 기록하면 된다. func 는 두 개의 pair 의 네 값에서 으뜸과 버금을 찾아 pair 로 돌려준다. tree 의 terminal node 는 입력값이 기록되어야 하므로 버금값은 입력되는 값보다 작은 아무 값이나 정하면 된다. 주어진 문제에서는 입력값이 자연수이므로 tree 의 기본값인 0 을 써도 상관없다. 음수가 허용되면 주석 처리한 부분을 살리면 된다. #include using namespace std; using pii=pair; int arr[100001]; pii tree[300000]; pii func(pii a, pii b){ pii res; int t; if(a.first>=b.first) {..

x 좌표는 오름차순, y 좌표는 내림차순으로 정렬. 정렬된 순으로 진행하면서 이전까지 기록한 y 좌표가 크거나 같은 것의 개수를 센다. 즉, 범위 안의 y 좌표를 효과적으로 세야하니까 segment tree 나 Fenwick tree 를 쓴다. 먼저 Fenwick tree 부터 #include using namespace std; using ll=long long; int sz; pair arr[75000]; int cpy[75000], bits[75001]; void upd(int p){ for(;p0;p&=p-1) ans+=bits[p]; return ans; } void solve(){ int n; scanf("%d", &n); for(int i=1;i