devbelly

문제 https://www.acmicpc.net/problem/2832 알고리즘 fenwick 풀이 감소하는 연속 부분 수열을 reverse를 몇번 해야 오름차순으로 만들 수 있는지 묻는 문제입니다. 주어진 순열중에서 연속한 내림차순이 있다면 해당 부분을 reverse함수를 통해 오름차순으로 만듭니다. 연속 부분 오름차순들이 여러개 만들어졌다면 이들 사이의 경계값은 길이가 2인 내림차순이 존재하게 됩니다. 길이가 2인 내림차순을 reverse하여 오름차순으로 정렬하는 것은 inversion을 counting하는 것과 일치합니다. $N$제한이 10만이므로 펜윅트리를 통해 빠르게 inversion을 세면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ..

문제 www.acmicpc.net/problem/14245 알고리즘 fenwick 풀이 구간 업데이트와 점 쿼리를 처리하는 문제입니다. 일반적인 펜윅트리는 점 갱신과 구간 쿼리를 처리하는 용도로 많이 사용됩니다. 구간 갱신을 사용하기 위해서는 일반적으로 lazy propagation을 떠올리기 쉽습니다. 하지만 구간 갱신을 처리하더라도 쿼리가 구간 쿼리가 아닌 점 쿼리만 이루어진다면 일반적인 펜윅트리의 변형으로도 가능합니다. 일반적으로 펜윅트리에서 배열 $A$에 대해 우리가 하는 연산은 다음과 같습니다. $update(i,v)$ = $A[i]$에 $v$만큼 더하기 $query(i)$ = $A[1]$~$A[i]$까지 합 구하기 다음과 같은 $B$배열을 만들면 구간 갱신과 점 쿼리가 가능합니다. $B[i]$..