본문 바로가기

세그먼트 트리

BOJ)2370 시장 선거 포스터 문제:icpc.me/2370 포스터를 붙이는 순서가 주어질 때 보이는 포스터의 수를 출력하는 문제이다. 포스터의 모든 x좌표와 y좌표를 좌표압축 한 뒤 포스터를 역순으로 보면서 이미 본 포스터는 업데이트 시켜주고 내가 보이는지 여부는 이미 업데이트 된 포스터들이 나를 완전히 가리는지 확인하면 된다. 이는 세그먼트 트리를 이용하여 업데이트 된 구간의 합을 찍어냄으로 판별 가능 하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include using namespace std;int n, seg[80040], lazy[80040],.. 더보기
BOJ)3172 현주와 윤주의 재미있는 단어 게임 문제:icpc.me/3172 어떤 단어가 x가 어떤 단어 y보다 사전순으로 앞서 있으면서 y를 뒤집은 y'이 x를 뒤집은 x'보다 앞서 있다면 두 단어는 서로 좋아하지 않는다고 한다. 단어가 10만개이기 때문에 brute force로 접근한다면 시간초과를 면치 못할 것이다. 그렇기 때문에 생각을 바꾸어서 기존의 문자열 기준으로 정렬을하여 번호를 매겨준 뒤 그 번호를 가진 상태로 문자열을 다 뒤집은 후 정렬을 해주고 앞에서 부터 보면 나보다 먼저 본 문자열 중에 나보다 할당 된 번호가 큰 문자열의 수를 세주면 된다. 이는 세그먼트 트리나 펜윅 트로로 효율적으로 해결할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#in.. 더보기
BOJ)1999 최대최소 문제: icpc.me/1999 n*n 행렬에 값이 주어져 있을 때 한 지점에서 부터 시작한 b*b 크기의 부분 행렬에서의 최댓값-최솟값을 출력하는 문제이다. 2차원 세그먼트 트리를 이용하면 O(K*NlogN)에 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include using namespace std;int n, b, k, minseg[251][250 * 4], maxseg[251][250 * 4], a[251][251];int minupdate(int *tree, int pos, int val, int node, int x,.. 더보기
BOJ)14577 일기예보 문제:icpc.me/14577 4가지 종류의 질의가 들어오는 문제이다. 지역 수 가 N 질의의 수가 M일 때 N,M이 10만까지 들어오므로 적어도 질의 하나당 log 시간에 해결해줘야 한다. 결국 3,4번 질의를 로그시간에 답해줘야 하는데 구간에 대한 질의이므로 우선 세그먼트 트리를 생각해낼 수 있다. 하지만 좌표 자체에 업데이트를 할 경우 좌표의 범위부터가 감당이 안된다. 그렇기 때문에 우리는 한 지역에 쌓일 수 있는 눈의 양에 업데이트를 해야한다. 나올 수 있는 눈의 양은 3번 쿼리의 경우 2개 1,2번 쿼리의 경우 1개 일 뿐이니 최대 2*M개 뿐이기 때문이다. 말을 어렵게 표현했는데 우선 쿼리를 오프라인으로 처리할거다. 모든 쿼리를 받은 뒤에 해당 질의 때 마다 나올 수 있는 모든 눈의 양을 저장.. 더보기
BOJ)2820 자동차 공장 문제: icpc.me/2820 문제를 잘 읽어보면 1번을 루트로 가지는 트리 구조를 이룬다는걸 알 수 있다. 그럼 상사 X의 부하들은 어떻게 구분할 수 있을까? 트리 구조이기 때문에 X에서 Y로 가는 경로는 오직 하나일 것이다. 이걸 이용하여 X지점에서 시작한 DFS가 끝날 때 까지 탐색되는 모든 노드들은 X의 부하라는걸 알 수 있다. 이를 이용하여 1번 노드에서부터 DFS를 돌려 정점의 번호를 새롭게 매겨준 후 DFS가 끝나는 지점(마지막 부하)의 번호까지 알게 된다면 직원에 대한 증가연산을 구간에 대한 증가 연산으로 치환시킬 수 있다, 구간에 대한 증가 연산으로 치환을 했으니 레이지 프로퍼게이션을 이용한 세그먼트 트리나 ,펜윅 트리 등을 이용하여 쿼리를 처리해주면 된다. 1234567891011121.. 더보기
BOJ)3770 대한민국 문제:icpc.me/3770 동해안과 서해안을 잇는 고속도로의 셋이 주어질 때 교차점의 수를 구하는 문제이다. 모든 고속도로를 받아서 동해안의 순서로 오름차순 정렬을 해준 뒤 동해안의 순서로 보면서 현재 보고 있는 고속도로보다 전에 봤던 고속도로 중 현재 고속도로보다 서해안이 큰 고속도로들의 수를 구해주면 된다. 이를 효과적으로 계산하기 위하여 세그먼트 트리를 사용해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include using namespace std;int t, n, m, k, x, y, seg[10000];long long r;int update(in.. 더보기
BOJ)9463 순열 그래프 문제:icpc.me/9463 두 순열이 주어질 때 같은 번호끼리 연결할 때 생기는 교점의 수를 구하는 문제이다. 우선 첫번째 순열의 순서를 기준으로 새로운 순열 A를 생성한다. 그리고 두번째 순열의 각 번호를 순열 A에 대입한 순열 B를 생성한다. 이제 순열 B에서 현재 보고있는 i보다 오른쪽에 있고 i로 인하여 만들어지는 교점의 수는 B[i]-1-(1~B[i]까지 이미 지나간 수들의 수)로 계산 가능하다. 1~B[i]까지 이미 지나간 수들의 수는 세그먼트 트리를 이용하여 관리할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std;i.. 더보기
BOJ)14428 수열과 쿼리 16 문제: icpc.me/14428 i j 가 주어질 때 Ai ~ Aj 까지의 최솟값의 인덱스를 출력하는 문제이다. 세그먼트 트리를 이용하여 구간의 가장 작은 위치의 인덱스를 저장해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #define INF 987654321using namespace std;int n, m, seg[400000], x, y, z, a[100001];int uquery(int pos, int node, int x, int y) { if (pos 1; int q1 = uquery(pos, node * 2, x, mid); int q.. 더보기
BOJ)10090 Counting Inversions 문제: icpc.me/10090 1~N의 숫자들로 구성 된 수열이 주어질 때 먼저 나온 수보다 늦게 나온 수가 더 작은 경우의 수를 구하는 문제이다. N이 100만이기 때문에 N^2 완전 탐색으로 해결하기에는 문제가 있다. 따라서 우리는 쿼리를 받는 순서대로 온라인으로 처리를 해줄 것이다. 우선 내가 현재 보는 수가 x라면 나보다 작은 수의 개수는 x-1개다 그러면 나보다 먼저 나온 수들 중 나보다 작은 수의 개수가 a개라면 x에 의하여 결정되는 경우의 수는 x-1-a가 된다. 따라서 우리는 세그먼트 트리를 이용하여 수열을 받을때마다 x보다 작은 수의 개수들을 구해주어 x-1-a를 답에 더해주고 x의 위치에 1을 업데이트 시켜주면 된다. 주의 할점은 답을 저장할 자료형을 long long으로 사용해야 한.. 더보기
BOJ)10277 JuQueen 문제: icpc.me/10277 C개의 코어가 있을 때 쿼리를 받아 3종류의 연산을 처리해주면 되는 문제이다. 단 코어의 하한선은 0이고 상한선은 N으로 입력으로 주어진다. 쿼리는 다음과 같다 change X S 코어X를 S만큼 증가시켜라groupchange A B S 코어 A부터 코어B까지 전부 S만큼 증가시켜라state X 코어X의 값을 출력하라 단, 코어를 증가시키다가 상한이나 하한에 다다를시 증가를 멈춘다. change나 groupchange 같은 경우 증가혹은 감소시킨 계수를 출력해야 하는데 우리는 코어를 증가시키다 상한이나 하한에 도달하는 경우를 판단해야한다. 따라서 우리는 구간에 대한 최댓값 최솟값을 세그먼트 트리로 관리하여 구간을 증가 시킬 시 상한혹은 하한에 도달하는지 여부를 판단하여 상.. 더보기

티스토리툴바