세그먼트 트리7 [백준] 22355- 말뚝 (c++) https://www.acmicpc.net/problem/22355 문제 요약N개의 말뚝이 일렬로 박혀있다. 말뚝마다 처음 높이, 높이를 높이는 비용, 높이를 낮추는 비용이 주어진다.연속한 K개 이상의 말뚝의 높이를 똑같이 만드는 데에 드는 비용의 최솟값을 구해라. 풀이 (NlogHlogH)세그먼트 트리삼분 탐색말뚝의 높이를 h로 만드는 데에 드는 비용을 그래프로 나타내면 아래로 볼록한 모양이다. 따라서 말뚝 구간의 높이를 h로 만드는데 드는 비용 그래프 또한 아래로 볼록하다. 삼분 탐색으로 최적의 높이를 구할 수 있다.각 말뚝의 높이를 h로 만드는 비용은 일차함수로 표현할 수 있는데 펜윅트리 두개로 여러 일차함수의 대한 쿼리를 처리할 수 있다. (계수를 관리하는 펜윅, 상수를 관리하는 펜윅)#inclu.. 2025. 4. 16. [백준] 12846 - 무서운 아르바이트 (c++) https://www.acmicpc.net/problem/12846 문제 요약성화의 편의점에서는 최저 일급 기준으로 급여를 지급하며, 연속으로 일해야 한다.준수는 n일 동안 최대 이익을 얻을 수 있도록 일해야 한다.최대 수익을 계산하라. 풀이 (NlogN)분할 정복세그먼트 트리일급을 히스토그램으로 표현해 보면 가장 큰 직사각형 문제랑 같아진다는 걸 알 수 있다.전체 구간을 시작으로 구간에서 가장 낮은 막대를 기준으로 분할정복할 수 있다.#include using namespace std;#define ll long long#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()#define mid (st+en>>1)int n;vector h.. 2025. 3. 17. [백준] 17131 - 여우가 정보섬에 올라온 이유 (c++) https://www.acmicpc.net/problem/17131 문제 요약좌표 평면에 점 N개가 주어진다. 세점 s,t,u가 s.xt.y 풀이 1 (NlogY) 세그먼트 트리스위핑처음에 떠오른 펜윅 두개를 관리하며 x축 스위핑을 하는 방법이다.펜윅 하나는 y에 대해 y보다 큰 점의 개수를 관리하고 다른 하나는 t.y가 y보다 작은 s,t 쌍의 개수를 관리한다. 그럼 현재 점이 u일때 s,t,u 쌍의 개수를 구할 수 있다. x좌표가 겹치면 안되기 때문에 x좌표가 같은 점끼리 묶어서 처리해야 한다.#includeusing namespace std;#define ll long longconst int N =4e5+5,mod=1e9+7;ll up[N],down[N];void uupdate(int x,int.. 2025. 1. 28. [백준] 2912 - 백설공주와 난쟁이 (c++) https://www.acmicpc.net/problem/2912 문제 요약난쟁이 N명이 있다. 각 난쟁이가 쓰고 있는 모자의 색깔이 주어진다. 쿼리로 구간이 주어지는데 그 구간의 과반수 이상의 난쟁이가 같은 색깔의 모자를 쓰고 있는지 구해라. 풀이 1 (Mlog^3N)머지 소트 트리머지 소트 트리로 구간에 특정 값이 과반수 이상 있는지는 log^2N의 시간복잡도로 구할 수 있다. 모든 색깔에 대해 과반수 이상 있는지 확인하는 건 시간초과이다. 후보 색깔을 줄여야 한다. 수열의 과반수 이상이 k이면 수열 가운데 값이 k이다. 또한 그 수열의 substring중 한 개 이상의 수열은 또 과반수 이상이 k이다. 이 성질을 이용해야 한다. 구간에 포함되는 노드 logN개에 대해 가운데 값들을 모두 후보로 잡는.. 2025. 1. 10. [백준] 2185 - 직사각형의 합집합 (c++) https://www.acmicpc.net/problem/2185IOI 1998 > Day 2 4번 문제 요약직사각형 여러개가 입력으로 주어진다. 직사각형의 합집합의 둘레를 구해라 풀이 (Nlog(max_coord))스위핑세그먼트 트리세그먼트 트리를 안 쓰고 N*(max_coord) 풀이도 충분히 돌아간다. 하지만 연습삼아 세그트리를 써서 시간복잡도가 좋은 풀이를 내봤다. x축 y축 나눠서 스위핑을 한다고 생각해보자 둘레가 갱신되는 건 길이에 변화가 생기는 순간이란 관찰을 할 수 있다. 구간안에 전체 길이를 세그로 구하면 길이가 달라질 때, 달라진 만큼 답에 더해주면 된다. 중복을 제외하고 길이를 구하는 테크닉은 이 블로그에 자세히 나와있다.https://ps.mjstudio.net/0-1-segment.. 2024. 11. 19. [백준] 3392 - 화성 지도 (c++) https://www.acmicpc.net/problem/3392 문제 요약직사각형이 N개 구어진다. 직사각형끼리 서로 겹칠 수 있다고 할 때 직사각형들이 차지하는 전체 면적을 구해라. 풀이 (Nlog(3e4))스위핑세그먼트 트리https://gkgkgkgkgkgkgk.tistory.com/21 [백준] 2672 - 여러 직사각형의 전체 면적 구하기 (c++)https://www.acmicpc.net/problem/2672 문제 요약직사각형이 N개 구어진다. 직사각형끼리 서로 겹칠 수 있다고 할 때 직사각형들이 차지하는 전체 면적을 구해라. 풀이 (N*(1e4))스위핑x좌표 기준으로 직사gkgkgkgkgkgkgk.tistory.com면적을 구하는 아이디어는 이 문제와 같다. 하지만 제한이 커서 세그먼트 .. 2024. 10. 30. 이전 1 2 다음