본문 바로가기

세그먼트 트리

BOJ)5480 전함 문제: icpc.me/5480 각 레이저가 파괴하는 전함의 무게의 최댓값을 출력하는 문제이다. 우리는 우선 쿼리를 전부 받아 오프라인으로 문제를 풀어볼거다. 일단 x좌표와 y좌표가 10억까지들어올수 있기 때문에 전함과 레이저의 x,y좌표를 모두 받아 각각 좌표압축 해준다. 이후 우리는 x와 y에 대한 세그먼트트리를 각각 생성하여 세그먼트 트리에 레이저의 인덱스의 최솟값을 저장할 것이다. 수직인 레이저는 x세그먼트 트리에 수평인 레이저는 y세그먼트 트리에 레이저의 인덱스를 해당 좌표에 최솟값 업데이트 시켜주면 된다. 이후 전함마다 각각 x,y세그트리에서 최솟값인 인덱스를 받는다 가장 작은 인덱스가 의미하는건 결국 그 전함을 파괴하는 레이저라고 보면 된다. 해당 레이저에 전함의 무게를 최댓값으로 업데이트 시.. 더보기
BOJ)10167 금광 문제: icpc.me/10167 직사각형 모양의 영역으로 금광을 개발 할 때 얻을 수 있는 최대 이익을 구하는 문제이다. 문제를 푸는데 상당히 고생했는데 KOI 2014 중등부 문제인걸 보고 어이가없어서 웃음만 나왔다... 일단 N이 3000이므로 N^2혹은 N^2logN 알고리즘을 사용해야 하는데 처음 생각한것은 x축기준으로 스위핑 하여 y축을 세그먼트 트리 구간합에 업데이트 시키는 작업을 순서대로 하는데이 때 이 작업은 전단계의 점들을 반드시 포함하게 되므로 모든점에 대해서 이 작업을 반복하는 것이다. 이 때 처음에는 최대 구간합을 구하기 위해서 이미 업데이트 된 모든 점이랑 비교하여 구간합의 최댓값을 구했는데 이렇게 할 경우 한점에서 업데이트한 후 구간합의 최댓값을 구하는데 O(NlogN) 여기에 .. 더보기
BOJ)1666 최대 증가 직사각형 집합 문제: icpc.me/1666 여러 직사각형이 주어졌을 때 이중 몇개의 직사각형을 골라서 집합을 만들것이다. 이때 집합의 조건은 집합의 임의의 두 원소를 선택했을 때 두 직사각형중 한 직사각형이 다른 한 직사각형보다 오른쪽 위에 있어야한다는 조건이다. 우선 각 원소를 왼쪽 아래 점의 x좌표 기준으로 스위핑하여 문제를 푸려고한다. 우리는 각 원소를 비교해나가며 쿼리를 처리하며 세그먼트 트리에 업데이트 할 것인데 이 때 비교는 왼쪽 아래 점과 하며 업데이트는 오른쪽 윗 점을 할것이다. x좌표 기준으로 정렬을 했기 때문에 우리는 세그먼트 트리에 y좌표의 위치에 업데이트 할 것이다. 이때 좌표압축을 사용해 노드를 줄인다. 하지만 우리는 비교는 왼쪽 아래 점 기준으로 하며 정렬도 왼쪽 아래 점 기준으로 하지만 업.. 더보기
BOJ)3392 화성 지도 문제: icpc.me/3392 지도가 주어졌을 때 전체 지도의 면적을 출력하는 문제이다. X,Y좌표가 최대 3만까지 들어오기 때문에 O(X*Y)완전 탐색으로 문제를 해결하기에는 무리가 있다. 우리는 지도의 세로축들을 쿼리로 관리하여 x좌표 ,y좌표1, y좌표2 그리고 끝나는 변인지 시작하는 변인지 변수로 관리를 해준다. 이제 쿼리들을 X좌표 기준으로 정렬을 해보자. 쿼리를 순서대로 볼건데 시작하는 변인 쿼리는 y1~y2구간을 1씩 증가시켜줄것이고 끝나는 변인 쿼리는 y1~y2구간을 1씩 감소시켜 줄것이다. 쿼리를 세그먼트 트리에 업데이트 해주기 전에 우리는 가장 최근에 처리한 쿼리의 x좌표와 현재 처리중인 x좌표의 차이를 dx라고 할때 현재 확인중인 x좌표까지의 면적을 dx*(업데이트 된 y좌표의 개수).. 더보기
BOJ)2336 굉장한 학생 문제:icpc.me/2336 N명이 학생이 세번의 시험을 치뤘을 때 A라는 학생이 B라는 학생보다 세번의 시험의 성적이 모두 좋다면 A가 B보다 '대단하다'고 한다. 어떤 학생 C가 자신보다 대단한 학생이 없을 경우 C는 '굉장하다'라고 한다. N명의 학생의 3번의 시험에서의 등수가 주어졌을 때 굉장한 학생의 수를 구하는 문제이다. 굉장한 학생을 다시 정의하자면 자기보다 세번의 시험을 전부 다 잘본 학생이 한명도 없는 경우이다. 우리는 굉장한 학생을 구하기 위해 첫번째 시험의 등수 기준으로 정렬을 할 것이다. 그리고 첫번째 시험을 잘 본 순서대로 쿼리를 처리할 것이다. 이러면 먼저 나온 학생이 적어도 그 뒤에 나온 학생들보다 1번째 시험을 잘봤다는 것은 자명한 사실이니 뒤에 나오는 학생들의 2,3번째 시.. 더보기
BOJ)1395 스위치 문제: icpc.me/1395 1~N번까지 스위치가 존재할 때 두가지 쿼리에 따른 일을 한다. 1. S~T까지 스위치를 반전 시키는 것2. S~T까지 켜져있는 스위치의 개수를 출력하는 것 우리는 세그먼트 트리의 구간합을 통하여 켜져있는 스위치의 개수를 쉽게 구할 수 있다. 하지만 1번 쿼리의 경우 구간에 대한 갱신이 일어나기 때문에 우리는 lazy propagation을 사용하여 업데이트를 시켜줘야만 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #define MAX_N 100000using namespace std;int n, m, seg[4 * MAX_N],.. 더보기
BOJ)10999 구간 합 구하기2 문제: icpc.me/10999 구간에 대한 합을 출력하는 문제이다. 그런데 쿼리중에 구간에 대한 갱신 연산을 하는 쿼리가 있다. 우리는 세그먼트 트리를 통해 구간에 대한 갱신과 합쿼리를 빠르게 처리 할 수 있지만 구간에 대한 갱신을 세그먼트 트리로만 하려고 한다면 갱신의 경우 최악의 시간복잡도는 O(NlogN)이 될것이다. 만약 쿼리가 전부 갱신만 들어온다면 시간 복잡도는 O(N(M+K)logN)로 당연히 시간초과를 보게 될 것이다. 그래서 우리는 lazy propagation을 이용하여 구간에 대한 갱신을 조금 더 빠르게 해주는 테크닉을 이용하여 문제를 풀어야만 한다. lazy propagation에 대한 설명은 여기에 친절하게 되어있다. 1234567891011121314151617181920212.. 더보기
BOJ)11505 구간 곱 구하기 문제:icpc.me/11505 구간에 대한 곱을 출력하는 문제이다. 값의 갱신이 빈번하게 일어나기 때문에 세그먼트 트리를 이용해주면 된다. 곱셈의 특성상 구간의 곱을 가지고 있으면 무수히 커질 수 있기 때문에 문제에서 모듈러연산을 요구한다. 이때 단순히 답에만 모듈러연산을 해준다면 노드가 가지고 있는 값이 오버플로우 될 수 있으므로 우리는 노드가 가진 값들을 업데이트 할 때 와 쿼리를 처리할 때도 모듈러연산을 해줘야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define MOD 1000000007#define MAX_N 1000000typedef long long .. 더보기
BOJ)5012 불만 정렬 문제: icpc.me/5012 iAk를 만족하는 경우의 수를 세는 문제이다. 우리는 j를 기준으로 생각해보자. 현재 j를 보고 있을 때 경우의 수에 해당할 수 있는 경우는 result = SUM [ (j보다 먼저 등장하고 Aj보다 큰 수) x (j보다 나중에 등장하고 Aj보다 작은 수) ] 으로 나타낼 수 있다. 따라서 우리는 쿼리를 다 받은 후 앞에서 부터 보면서 j보다 먼저 등장하면서 Aj보다 큰 수들을 먼저 기록 한 후 다시 한번 뒤에서부터 보면서 j보다 늦게 등장하면서 Aj보다 작은 수들을 기록해준 뒤 곱해주어 더한값을 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #in.. 더보기
BOJ)3002 아날로그 다이얼 문제: icpc.me/3002 N개의 다이얼이 주어졌을 때 구간이 주어지면 구간의 합을 구한뒤 구간의 수를 전부 1씩 증가시켜주는 문제이다. 얼핏보면 구간에 대한 증가연산과 구간합을 출력하면 되니 레이지 프라퍼게이션을 이용한 구간합으로 바로 해결할 수 있을것 같지만 문제는 다이얼이기 때문에 9를 증가시키면 0이 된다는 것이다. 결국 0~8의 숫자는 증가시킬 경우 1씩증가하게 되지만 9는 증가시킬 경우 오히려 -9가 되버린다. 이래서 구간에 대한 합을 한번에 노드에 저장하고 있을 경우 증가연산이 애매해질 우려가 있다. 따라서 우리는 구간마다 노드를 10개씩 만들어 0~9까지의 개수를 저장하여 값을 증가시키는 경우 0~9 ->(0+x)%10~(9+x)%10까지로 쉬프트 시킬것이다. 물론 구간에 대한 증가가 .. 더보기

티스토리툴바