세그먼트트리

1. 문제 풀이오늘 풀어본 문제는 백준 18346번 수열과 쿼리 37입니다. 문제의 유형은 세그먼트 트리입니다. 세그먼트 트리를 이용해 짝수의 개수와 홀수의 개수를 구간별로 관리하면서 풀이했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef vector vti; typedef vector vtl;typedef vector..

1. 문제 풀이 오늘 풀어본 문제는 백준 12837번 가계부 (Hard)입니다. 문제의 유형은 세그먼트 트리입니다. 세그먼트 트리는 리프 노드의 값을 변경하는 갱신 연산과 어떤 구간이 주어졌을 때, 그 구간의 합을 구하는 쿼리 연산이 있습니다. 이 두 연산을 단순하게 사용하기만 하면 AC를 받을 수 있는 문제이므로 세그먼트 트리에 대해서 공부하고 구현도 해보았다면 연습 문제로 풀어보기 좋은 문제 같습니다. 주의할 점은 갱신 연산을 할 때, 값을 바꾸는 것이 아니라 + 연산을 해야 한다는 점입니다.2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair ..

1. 문제 풀이 세그먼트 트리 자료구조를 사용해서 문제를 풀었습니다. 배열 정보를 입력 받아 { x, i }와 같은 pair 타입으로 배열에 저장합니다. x는 배열의 값이고, i는 x의 index입니다. 이를 오름차순으로 정렬합니다. 이 때, x의 값이 같을 때에는 i가 큰 순서가 먼저 오게 custom_sort가 필요합니다. 그 이유는 중복된 값을 수열의 길이에 추가하는 것을 방지하기 위함입니다. 다음 배열의 가장 작은 값부터 순회를 시작합니다. [ 0, i ] 범위에서 LIS의 최대 길이를 구한 다음, +1한 값으로 세그먼트 트리를 갱신해줍니다. 이를 모두 완료했다면 세그먼트 트리의 루트 값이 입력으로 주어진 배열에서 가장 긴 증가하는 부분 수열이 됩니다. 2. 코드#include using name..