Fenwick tree (7) 썸네일형 리스트형 [ICPC] 백준 23245 - Similarity https://www.acmicpc.net/problem/23245 대회 당시 내가 푼 문제임에도 불구하고 귀찮다는 이유로 안 쓰고 있었는데 다른 글들을 둘러보니 나와는 다른 방향으로 푼 거 같아 작성하고자 한다. 사실 여기서 적을 것은 별로 없다. 주어진 수열 쌍을 적절히 오름차순으로 정렬하고 좌표 압축을 수행하면 아래 문제와 조건이 동일해진다. https://www.acmicpc.net/problem/17409 17409번: 증가 수열의 개수 첫째 줄에 N, K가 주어진다. 둘째 줄에 수열 A1, A2, ..., AN이 주어진다. www.acmicpc.net 그러면 위 문제에서 k가 3인 버전으로 생각하고 세그먼트 트리로 LIS 카운팅 DP를 수행하면 된다. 자세한 풀이는 여기를 참고하라. 그런데 다.. 백준 1615 - 교차개수세기 https://www.acmicpc.net/problem/1615 힌트 더보기 이 문제를 풀기 위해선 inversion counting에 대한 지식이 있어야 한다. 문제에 주어진 형태처럼 교차 그래프가 주어졌을 때의 LIS 문제를 풀어본 경험이 있다면 이것도 비슷하게 접근할 수 있다. 생각해보자! 풀이 더보기 교차 그래프가 주어지고 몇개의 간선이 교차하는지 알아내야 한다. 어느 쪽 노드 집합을 기준으로 정렬을 한 후 반대 쪽 노드 집합들의 나열 형태를 보면서 교차 간선의 개수를 세보자. 그러면 inversion counting의 형태를 띄는 것을 관찰할 수 있다. 자세한 설명은 동일한 유형의 문제 풀이를 참조하라. 그대로 inversion counting의 개수를 출력해주면 된다. 전체 코드 #pragm.. 백준 13555 - 증가하는 부분 수열 https://www.acmicpc.net/problem/13555 17409 - 증가 수열의 개수와 풀이가 같다. 다만 17409와 달리 원소의 상한과 수열의 길이가 불일치라는 것과 세그먼트 트리가 아닌 펜윅 트리로만 풀린다는 점을 유의하여 구현하도록 한다. 전체 코드 더보기 #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; #define mod 5000000 int n, k; int dp[51][100001]; int sum(int pos, int seq) { if (!seq) return 1; int ret = 0;.. [ICPC] 백준 5012 - 불만 정렬 https://www.acmicpc.net/problem/5012 문제를 해결하기 위해 펜윅 트리에 다음 정보를 관리할 것이다. 현재 순회 중인 index에 해당하는 값 val 이상의 값이 출현하는 횟수 그러면 val을 pivot으로 할 때 구간은 다음과 같이 표현될 수 있다. [val보다 작은 index에서 val 이상의 값이 나타나는 횟수), val, (val 보다 큰 index에서 val 이상의 값이 나타나는 횟수] 이렇게 되면 왼쪽 구간에서 큰 수를 선택하는 경우와 오른쪽 구간에서 작은 수를 선택하는 경우를 곱셈법칙으로 계산하여 왼쪽 구간의 값 * (오른쪽 원소의 갯수 - 오른쪽 구간의 값)를 각 pivot마다 더해주어 답을 구할 수 있다. 하지만 이렇게 하면 왼쪽 구간에서 val보다 큰 값이 있.. [ICPC] 백준 9463 - 순열 그래프 https://www.acmicpc.net/problem/9463 각 편에서 번호가 같은 정점끼리 연결했을 때 생기는 교차점으로 순열 그래프를 구성한다고 한다. 우리는 교차점의 개수를 구해야 되므로 문제에서 첫번째 그림을 보고 3770번 문제와 같은 흐름으로 inversion counting을 생각할 수 있다. 다만 이 문제는 주어진 입력에서 번호가 같은 정점끼리 연결하는 것이므로 이를 적절히 변환해줄 필요가 있다. 주어지는 첫번째 노드 집합을 index에 매칭하여 각 숫자가 어느 index에 대응하는지 배열로 저장한다.(mp[val] = idx) 두번째 노드집합에서는 index와 첫번재 mp배열에서 해당 노드 숫자의 index를 가져와 pair로 짝지어서 배열이나 선형 자료구조에 저장한다. 그렇게 되면.. 이전 1 2 다음
