목록세그먼트 트리 (19)
알고리즘 모음(C++)
백준 14268 - 회사 문화 2(C++)
문제 링크입니다. https://www.acmicpc.net/problem/14268 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M;long long Tree[100001 * 4];long long left_tree[100001 * 4], right_tree[100001 * 4];long long lazy[100001 * 4];vector connect[100001];void make_order(int node, int &cnt){ left_tree[node] = ++cnt; for(int i = 0;..
백준 14245 - XOR(C++)
문제 링크입니다. https://www.acmicpc.net/problem/14245 해당 문제를 풀기 위해선 XOR의 기본적인 특징을 하나 알아야합니다. 예를 들어, 10011 ^ 11100을 한다면 01111이 나옵니다. 이때, 11100을 다시 XOR을 한다면 01111 ^ 11100 = 10011이 됨으로 다시 원래대로 돌아옴을 알 수 있습니다.-> "같은 수를 짝수번 XOR 한다면, 원상태로 돌아온다"가 됩니다. 그러므로, 구간의 값을 가진 트리에 XOR을 한다면 구간의 길이를 통해서 XOR 여부를 확인해주면 됩니다. 쿼리의 개수가 크니, 느리게 갱신되는 세그먼트 트리를 사용하고, 이때 사용되는 lazy 배열에 해줘야하는 XOR 값을 계속 XOR 해주면, 0 또는 XOR 값으로만 남아 있을 ..
백준 12844 - XOR(C++)
문제 링크입니다. https://www.acmicpc.net/problem/12844 해당 문제를 풀기 위해선 XOR의 기본적인 특징을 하나 알아야합니다. 예를 들어, 10011 ^ 11100을 한다면 01111이 나옵니다. 이때, 11100을 다시 XOR을 한다면 01111 ^ 11100 = 10011이 됨으로 다시 원래대로 돌아옴을 알 수 있습니다.-> "같은 수를 짝수번 XOR 한다면, 원상태로 돌아온다"가 됩니다. 그러므로, 구간의 값을 가진 트리에 XOR을 한다면 구간의 길이를 통해서 XOR 여부를 확인해주면 됩니다. 쿼리의 개수가 크니, 느리게 갱신되는 세그먼트 트리를 사용하고, 이때 사용되는 lazy 배열에 해줘야하는 XOR 값을 계속 XOR 해주면, 0 또는 XOR 값으로만 남아 있을 ..
백준 1395 - 스위치(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1395 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다. 처리할 일의 개수가 10^5이기에 모든 경우를 계속 갱신한다면 시간 초과가 생길 것입니다.따라서, 바꾸는 정보를 기억해 놨다가 나중에 바꿔주는 느리게 갱신되는 방법을 사용해야 합니다. 단체로 바꿨을 때, 켜지는 전구의 수는 '해당 구간 전체 전구 수 - 현재 켜진 전구 수' 입니다. lazy 배열의 값이 홀수일 때만, 전구의 상태를 바꿔주면 된다는 것을 유의해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #inclu..
백준 16975 - 수열과 쿼리 21(C++)
문제 링크입니다. https://www.acmicpc.net/problem/16975 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다. 주어지는 쿼리의 수가 많기에 일반적으로 값을 바꾸는 세그먼트 트리를 사용한다면 시간초과가 생길 가능성이 높습니다.따라서, 느리게 갱신되는 세그먼트 트리를 이용해 주시면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M;long long Index[100001];long long Tree[100001 * 4];long long lazy[100001 * 4];l..
백준 1849 - 순열(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..
백준 10999 - 구간 합 구하기 2(C++)
문제 링크입니다. 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..
백준 2465 - 줄 세우기(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2465 세그먼트 트리를 이용한 문제입니다. 수열이 하나 주어지고, 해당 수열에서의 키 순서가 주어질 때, 키 순서에 맞는 수열을 찾는 문제입니다. 먼저, 자신보다 키가 작거나 같은 학생을 알기 위해서 오름차순 정렬을 해줍니다. 오름차순 정렬을 해줬으면, 자신이 어디에 들어가야 할지를 뒤에서부터 확인을 해줍니다.(키 순서가 0 1 0 0 3 2 6 7 4 6 9 4 이니 4에서부터 채워줍니다.) 뒤에서 부터 채우는 이유는 앞에서 부터 채울 경우 0을 채워야 하는데, 해당 값이 정확하지 않기 때문입니다.반대로 뒤에서 부터 채울 경우, 값이 0이 아닌 것부터 채우기 때문에 어떤 값을 먼저 채워야할지 명확해지기 때문입니다. 어떤 값이 ..
백준 14438 - 수열과 쿼리 17 (C++)
문제 링크입니다. https://www.acmicpc.net/problem/14438 세그먼트 트리를 이용한 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #include #define INF LLONG_MAXusing namespace std;int N, M;long long Index[100001];vector Tree;long long segment_tree(int st, int fin, int node) { if (st == fin) return Tree[node] = st; int mid = (st + fin) /..
백준 14428 - 수열과 쿼리 16(C++)
문제 링크입니다. https://www.acmicpc.net/problem/14428 세그먼트 트리를 이용한 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #include #define INF LLONG_MAXusing namespace std;int N, M;long long Index[100001];vector Tree;long long segment_tree(int st, int fin, int node) { if (st == fin) return Tree[node] = st; int mid = (st + fin) /..
백준 1725 - 히스토그램(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1725 세그먼트 트리를 이용해 풀었습니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면, (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의 위치..
백준 6549 - 히스토그램에서 가장 큰 직사각형(C++)
문제 링크입니다. https://www.acmicpc.net/problem/6549 세그먼트 트리를 이용해 푸는 문제입니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면, (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의..