devbelly

문제 www.acmicpc.net/problem/18874 알고리즘 segment tree 풀이 $j$보다 긴 머리카락들이 $j$가 될 때, badhair의 수를 구하는 문제입니다. 관찰이 조금 필요한 문제입니다. 우선 머리카락 길이가 변하는 것을 생각하지 않고 counting inversion을 할 때 브루트포스로 하면 $N^2$이 필요하고 문제에서 $N$제한은 10만이므로 $NlogN$에 inversion을 셀 수 있는 세그먼트 트리를 이용해야합니다. 쿼리($j$)마다 머리카락 길이를 업데이트를 하려면 아무리 빨리한다 하더라도 $O(N)$보다 빠를 순 없고 inversion을 세면 결국 시간초과입니다. 문제의 핵심은 $j$보다 긴 머리카락들이 $j$가 될 때, badhair을 발생시키는 머리카락들은 ..

문제 www.acmicpc.net/problem/17408 알고리즘 segment tree 풀이 점 갱신과 구간 사이의 두 값의 합의 최댓값을 묻는 문제입니다. 두 번째 쿼리는 세그먼트 트리에 최댓값을 저장하면서도 추가적으로 최댓값의 인덱스를 저장한다면 해결가능합니다. 주어진 범위가 $l, r$일 때, $query(l,r)$을 사용해서 최댓값 $M$과 인덱스 $idx$를 얻었다면 $query(l,idx-1)$와 $query(idx+1,r)$을 사용해 두 번째로 큰 값을 구하면 됩니다. 코드를 간결하게 하려고 $cmp$함수를 작성해 사용했습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1..

문제 www.acmicpc.net/problem/20052 알고리즘 segment tree 풀이 괄호 문자열이 주어지고 쿼리들이 주어졌을 때 부분 문자열이 올바른 괄호 문자열인지를 묻는 문제입니다. '('을 1로 생각하고 ')'을 -1로 생각했을 때, 올바른 괄호 문자열은 다음과 같은 특징을 갖고 있습니다. 1. 괄호문자열을 구성하는 문자들의 합은 0이다. 2. 문자열의 길이를 S라고 할 때, 처음부터 $i (1\leq i \leq S-1)$까지의 문자들의 합은 음수가 되어선 안된다. 1번 조건은 '('의 등장 횟수와 ')'의 등장 횟수가 일치함을 묻고 있습니다. 2번 조건은 괄호 문자들이 짝을 올바르게 구성하고 있는지를 묻고 있습니다. 만약 주어진 괄호 문자열이 ")(" 라면 총합은 0이 될지언정 올바..