알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1849 이분 탐색을 이용한 세그먼트 트리 문제입니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N;int Tree[100001 * 4];int remake[100001 * 4];int Rank[100001 * 4];int ans[100001 * 4];void make_tree(int node, int st, int fin){ if(st == fin) { Tree[node] = 1; return; } int left = nod..

문제 링크입니다. https://www.acmicpc.net/problem/10999 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.느리게 갱신되는 세그먼트 트리는 해당 링크를 참조해주세요. https://www.acmicpc.net/blog/view/26 느리게 갱신되는 세그먼트 트리를 사용할 수 있다면 바로 구할 수 있는 문제였습니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M, K;long long Index[1000001];vector Tree;vector lazy;long long se..

문제 링크입니다. https://www.acmicpc.net/problem/2465 세그먼트 트리를 이용한 문제입니다. 수열이 하나 주어지고, 해당 수열에서의 키 순서가 주어질 때, 키 순서에 맞는 수열을 찾는 문제입니다. 먼저, 자신보다 키가 작거나 같은 학생을 알기 위해서 오름차순 정렬을 해줍니다. 오름차순 정렬을 해줬으면, 자신이 어디에 들어가야 할지를 뒤에서부터 확인을 해줍니다.(키 순서가 0 1 0 0 3 2 6 7 4 6 9 4 이니 4에서부터 채워줍니다.) 뒤에서 부터 채우는 이유는 앞에서 부터 채울 경우 0을 채워야 하는데, 해당 값이 정확하지 않기 때문입니다.반대로 뒤에서 부터 채울 경우, 값이 0이 아닌 것부터 채우기 때문에 어떤 값을 먼저 채워야할지 명확해지기 때문입니다. 어떤 값이 ..