알고리즘 공부방

문제 https://www.acmicpc.net/problem/2243 i번째 맛의 사탕을 추가/삭제 하는 쿼리와, 상자 안에 들어있는 사탕들 중 k번째로 맛있는 사탕을 뽑는 쿼리를 처리하는 문제이다. 풀이 각 사탕의 맛을 인덱스로 하는 펜윅 트리로 쿼리를 처리한다. 펜윅 트리는 추가/삭제 쿼리를 $O(logN)$ 안에 할수 있다. 두번째 k번째 사탕을 뽑는 쿼리는 1~i까지의 사탕의 개수에 대해서 이분탐색을 해주면 된다. 사탕의 개수를 묻는 쿼리가 $O(logN)$, 이분탐색이 $O(logN)$ 이므로 2번째 쿼리를 $O(log^2N)$ 안에 처리해 줄수 있다. 시간 복잡도 : $O(Qlog^2N)$ #include using namespace std; typedef long long ll; typed..

우선, $O(N^2)$ DP 풀이부터 살펴 보자. $dp[i]$ = $0$ ~ $i$ 구간에서 $i$를 끝으로 하는 lis의 최대 길이 $dp[i]$ = $0$ ~ $i-1$ 의 $j$ 에 대하여 $arr[i]>arr[j]$를 만족하고, $dp[j]+1$의 최대값을 만족한다. 여기서는 구현할 때 처음에 NEGINF, 끝에 INF 를 추가해서 구현하였고, 동시에 전 단계로의 선택 과정을 담아 복원까지 했다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1000; const int INF = numeric_limits::max(); const int NEGINF = ..