개인사

리뷰 업데이트를 통해 세그먼트 트리를 확장하고 구간합을 구하는 문제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..

리뷰 업데이트를 느리게 갱신하며 구간 누적합을 구하는 문제 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..

리뷰 수열의 특정 구간에 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 : 수열..

리뷰 느리게 갱신되는 세그먼트 트리의 기초 문제, 쿼리가 구간합이 아닌 특정 인덱스를 출력하는 문제이다.https://www.acmicpc.net/problem/16975 문제 풀이전역 변수MAX_N : 노드의 최대 개수를 지정할 상수 변수, 10만으로 초기화 한다.nodes : 수열의 정보를 저장할 배열, 크기는 MAX_N으로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4로 초기화 한다.lazy : 느린 업데이트 정보를 저장할 배열, 크기는 MAX_N * 4로 초기화 한다.n, m : 수열의 크기 n, 쿼리의 개수 m을 저장할 변수 함수1. buildvoid build(ll node, ll start, ll end) nodes 수열을 갖고 tree배열에 세그먼트 ..

리뷰 lazy propagate를 배우고 처음으로 문제에 접목해 봤다, 함수 구현보단 정수형 타입때문에 애를 좀 먹었다.https://www.acmicpc.net/problem/10999 문제 풀이전역변수MAX_N : 배열의 크기를 초기화 할 상수형 long long타입 변수nodes : 수열의 정보를 받아 저장할 배열 크기는 MAX_N으로 초기화tree : 세그먼트 트리 정보를 저장할 배열 크기는 MAX_N * 4로 초기화lazy : 업데이트 갱신용 트리 정보, tree와 같은 구조를 가진다.n, m, k : 수열의 길이를 나타낼 n, 업데이트 쿼리의 개수 m, 구간합 출력 쿼리의 개수 k함수1. buildvoid build(ll node, ll start, ll end) 세그먼트 트리를 빌드해 준다...

리뷰 세그먼트 트리를 통해 수열의 특정 구간의 첫번째 최대값과 두번째 최대값을 구하고 그 합을 구해 출력하는 문제https://www.acmicpc.net/problem/17408 문제 풀이전역 변수MAX_N : 노드의 최대 개수 10만을 상수형 정수타입으로 설정해 준다.nodes : 수열의 정보를 담을 배열, 크기는 MAX_N으로 설정한다.tree : 최대값과 인덱스를 담을 정수형 pair 배열, 크기는 MAX_N * 4로 설정한다.n, m : 노드의 개수 및 쿼리의 개수 정보를 담을 변수 함수1. 최대값을 갖는 세그먼트 트리를 만드는 함수 void build(int node, int start, int end) 리프 노드 도달 시 배열의 값과 인덱스를 저장해 준다.이후 탐색을 통해 위로 올려주며 각 ..

리뷰 두 노드에서 출발해 LCA에 달할때 까지 도로 중 가장 짧은 거리와 가장 긴 거리를 구하는 문제https://www.acmicpc.net/problem/3176 문제 풀이도시의 최대 개수는 10만이므로 MAX_N을 10만 1로, LOG를 MAX_N을 LOG2를 취한 값 보다 크게 20으로 설정한다.도시의 개수 n과 쿼리의 개수 k를 전역 변수로 설정한다.부모 도시를 담을 배열par, 짧은 거리 및 긴 거리를 저장할 배열 mn, mx을 MAX_N * LOG 크기로 설정한다.깊이를 담을 배열dep, 유니온 파인드용 배열 nodes를 MAX_N크기로 설저어한다.인접 리스트 정보를 담을 구조체 Link를 만들어 주고 Link타입 벡터 links를 MAX_N크기로 설정한다.n값을 입력 받고 1~n 도시를 각..