개인사

리뷰https://www.acmicpc.net/problem/14288오일러 경로 테크닉을 구한 인덱스를 기준으로 세그먼트 트리를 양 방향으로 업데이트를 진행하며 구간합을 구하는 문제 전역 변수MAX_N : 직원의 최대 수를 저장할 정수형 상수 변수n, m : 직원의 수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 mup_tree : 상사 방향으로 칭찬값을 저장할 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4down_tree : 부하직원 방향으로 칭찬값을 저장할 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4lazy : 세그먼트 트리에 갱신될 업데이트 값을 저장할 배열, 크기는 MAX_N * 4lst : 각 직원간의 상하 관계를 인접리스트 형태로 저장할 정수형 벡터 배열, 크..

리뷰 오일러 경로 테크닉으로 세그먼트 트리의 노드를 재정의 하고 누적합을 구하는 문제https://www.acmicpc.net/problem/14287 전역 변수MAX_N : 직원의 최대 개수를 저장할 정수형 상수 변수n, m : 직원의 개수를 저장할 정수형 변수 n, 쿼리의 개수를 저장할 정수형 변수 mtree : 세그먼트 트리 정보를 담은 정수형 배열, 크기는 MAX_N * 4로 초기화lst : 오일러 경로 테크닉에 사용할 인접 리스트, 정수형 벡터 타입으로 크기는 MAX_N으로 초기화it : 오일러 경로에서 각 직원의 탐색 시작 시간을 저장할 정수형 배열, 크기는 MAX_N으로 초기화ot : 오일러 경로에서 각 직원의 탐색 종료 시간을 저장할 정수형 배열, 크기는 MAX_N으로 초기화timer : ..

리뷰 구간 대체 업데이트, 구간 합, 느린 갱신, 오일러 경로 테크닉을 활용해야 하는 문제https://www.acmicpc.net/problem/18437 전역 변수n, m : 직원의 수 n, 쿼리의 수 mMAX_N : 주어지는 n값의 최대치를 나타낼 정수형 상수 변수, 100001로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화lazy : 세그먼트 트리 업데이트 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화path : 부하 직원을 인접리스트로 저장할 정수형 벡터, MAX_N크기로 초기화it : 서브 트리에서 해당 노드에 진입한 시간을 기록할 정수형 배열, MAX_N크기로 초기화ot : 서브 트리에서 해당 노드에서 빠져나온 시간을 기록할 ..

리뷰 오일러 경로 테크닉에 대한 개념을 이해하게 된 문제일반적인 Lazy propagation을 통한 풀이는 인덱스를 지정하기가 불가능해 보인다.https://www.acmicpc.net/problem/14268 전역 변수MAX_N : n값의 최대치를 저장할 정수형 상수 변수, 크기는 10만 1로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, 크기는 MAX_N * 4로 초기화lazy : 세그먼트 트리의 업데이트 정보를 저장할 정수형 배열, 크기는 MAX_N * 4로 초기화n, m : 직원의 수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 mpath : 직원간의 상하 직속 정보를 인접리스트 형태로 저장할 정수형 벡터, 크기는 MAX_N으로 초기화it : 서브 트리의 시작시간(세그먼트..

리뷰 업데이트를 통해 세그먼트 트리를 확장하고 구간합을 구하는 문제https://www.acmicpc.net/problem/3653 전역 변수tc, n, m : 테스트 케이스의 개수 tc, 각 테케의 DVD의 수 n, 각 테케의 쿼리의 수 mlst : DVD의 초기정보와 인덱스 정부를 담은 정수형 벡터tree : 세그먼트 트리의 구간합 정보를 담은 정수형 벡터 함수1. updatevoid update(int node, int s, int e, int idx, int val) 세그먼트 트리의 특정 인덱스의 값을 교체하고 구간합을 업데이트 하는 함수val은 1과 -1이 올 것이며 음수가 올 경우는 주어지지 않는다. 2. queryint query(int node, int s, int e, int L, int..

리뷰 서로 교차하는 케이블 쌍의 개수를 구하고 출력하는 문제https://www.acmicpc.net/problem/7578 전역 변수MAX_N : 입력 되는 노드의 최대 개수를 의미하는 정수형 상수 변수 500001로 초기화 해준다.nodes : 입력 받은 노드의 정보를 저장할 정수형 배열, MAX_N크기로 설정한다.index : 교차하기 위한 노드 정보를 저장할 정수형 배열, index를 값으로, value를 순서로 저장한다, MAX_N * 2크기tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 설정한다.n, ans : 노드의 개수를 저장할 변수 n, 정답을 저장하고 출력할 변수 ans 함수1. updatevoid update(ll node, ll s, ll e, ll i..

리뷰 업데이트를 느리게 갱신하며 구간 누적합을 구하는 문제 int 범위를 초과하므로 long long타입을 사용해 줘야 한다.https://www.acmicpc.net/problem/15967 전역 변수n, q1, q2 : 노드의 개수 n, 출력 쿼리의 개수 q1, 업데이트 쿼리의 개수 q2nodes : 노드의 정보를 저장할 정수형 배열, 크기는 100만으로 세팅tree : 세그먼트 트리 정보를 저장할 정수형 배열, 크기는 400만으로 세팅lazy : 업데이트 정보를 저장할 정수형 배열, 크기는 400만으로 세팅 함수1. buildvoid build(ll node, ll s, ll e) nodes배열을 사용하여 구간 합을 저장할 세그먼트 트리를 만드는 함수 2. propagatevoid propagate..

리뷰 세그먼트 트리를 응용하여 히스토그램 상에서 가장 큰 면적을 구하는 문제https://www.acmicpc.net/problem/6549 전역 변수lst : 히스토그램의 높이 정보를 저장할 정수형 배열, 최대 히스토그램 크기 10만으로 초기화 해준다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, lst의 4배 40만으로 크기를 초기화 해준다.n : 히스토그램의 최대 갯수를 저장할 정수형 변수  함수1. initvoid init() 각 테스트 케이스 마다 lst와 tree를 0으로 초기화 해주는 함수 2. inputvoid input() 데이터를 입력 받고 히스토그램 높이 정보를 lst배열에 초기화 해주는 함수 3. buildvoid build(ll node, ll start, ll end) ..

리뷰 세그먼트 트리의 기초가 되는 문제인듯 싶다, 구간 업데이트 쿼리가 아닌 리프 노드까지 도달해야 하는 문제수열과 쿼리 시리즈 부터 풀다보니 이런 기초 세그를 응용하는 문제가 약해서 생각의 폭을 넓혀야 겠다 ㅠhttps://www.acmicpc.net/problem/2243 전역 변수tree : 세그먼트 트리 정보를 저장할 정수형 배열, 사탕의 맛 개수가 최대 100만이므로 400만 이상의 크기로 세팅한다. 함수1. updatevoid update(int node, int start, int end, int idx, int val) 매개변수 idx의 맛을 가진 사탕의 개수를 val만큼 더해준다.val에는 음수가 올 수 있으나 문제에 없는 사탕을 꺼내는 경우와 같은 잘못된 입력은 주어지지 않는다. 라고 ..

리뷰 수열의 특정 구간에 XOR연산을 진행하고, 특정 인덱스의 값을 뽑아 출력하는 문제https://www.acmicpc.net/problem/14245해당 문제의 심화 버전으로 구간에 xor를 적용하여 출력하는 문제가 있다. [P3] 백준 12844번 XOR C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리리뷰 XOR연산에 대해 재정립 하는 시간이 되었다.https://www.acmicpc.net/problem/12844 전역 변수MAX_N : 노드의 최대 개수를 저장할 인트형 상수 정수, 50만으로 초기화 해준다.nodes : 노드의 정보를 저장할zzzz955.tistory.com   전역 변수MAX_N : 노드의 최대 개수를 정의할 정수형 상수 변수, 50만으로 초기화 해준다.nodes : 수열..