개인사

리뷰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 : ..

리뷰 오일러 경로 테크닉에 대한 개념을 이해하게 된 문제일반적인 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 : 서브 트리의 시작시간(세그먼트..

리뷰 XOR연산에 대해 재정립 하는 시간이 되었다.https://www.acmicpc.net/problem/12844 전역 변수MAX_N : 노드의 최대 개수를 저장할 인트형 상수 정수, 50만으로 초기화 해준다.nodes : 노드의 정보를 저장할 정수형 배열, MAX_N크기로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화 한다.lazy : 업데이트 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화 한다.n, m : 노드의 개수를 저장할 정수 변수 n, 쿼리의 개수를 저장할 정수 변수 m 함수1. buildvoid build(int node, int start, int end) 세그먼트 트리를 초기화 해주는 함수 2. propagatevoid ..

리뷰 느리게 갱신되는 세그먼트 트리 문제 치고 굉장히 짧고 쉬운 문제!https://www.acmicpc.net/problem/1395 전역 변수MAX_N : 스위치의 최대 개수를 정의할 정수형 상수 변수tree : 세그먼트 트리 정보를 저장할 배열 MAX_N * 4 크기로 초기값은 0이다.lazy : 업데이트 갱신을 적용하기 위한 트리 배열 MAX_N * 4 크기로 초기값은 0이다.n, m : 스위치의 개수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 m 함수1. propagatevoid propagate(int node, int start, int end) 현재 노드에 갱신이 필요하다면 갱신을 진행하고 자식 노드에 지연 업데이트를 기록하는 함수이다.현재 노드에 갱신이 필요하다면 구간의 길이 - 자신..