MathTrauma

문제 링크 : 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/13547 13547번: 수열과 쿼리 5 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. www.acmicpc.net 구간에 관한 질의에 두 부류의 대응이 있다. 하나는 구간들을 관리하는 세그먼트 트리같은 자료구조를 사용하는 것이고, 다른 하나는 앞선 질의를 위해 구간을 조사한 결과를 다음 질의에 재사용 가능하게 만드는 것이다. (후자의 수법을 쓰려면 질의를 사이에 자료의 변경이 없어야 한다. 자료 변경이 없다는 전제하에 질의를 재구성해서 시간을 절약하는 것을 off-line 쿼리라고 부르..

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

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

문제 링크 : 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, ..

닫힌 구간 [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..