세그트리8 BOJ 3392 - 화성지도 (세그트리 응용) https://www.acmicpc.net/problem/3392 코드는 다음 블로그의 코드를 많이 참조했습니다. https://jason9319.tistory.com/58 일반적인 세그트리의 형태를 따르지 않고, 세그먼트트리의 구조를 이용하여 풀 수 있는 문제. 좌표가 최대 30000인 2차원 평면 상에 최대 1e4개의 직사각형이 주어질 때, 직사각형들이 이루는 영역의 크기를 구하라 x좌표가 증가하는 순서대로 막대기들을 볼 때, "이전 x좌표와의 차 dx"와 "y좌표들의 psum이 1이상인 곳의 개수"를 곱해나가면 된다. 지금 막대기가 [y1,y2)일 떄 이 막대기가 시작 막대기인 경우 해당구간을 모두 +1, 끝 막대기인 경우 해당구간을 모두 -1해주며 배열을 유지해 나간다고 생각해야 한다. 이걸 la.. 2020. 6. 6. BOJ 15977 - 조화로운 행렬 (분할정복, 세그트리) https://www.acmicpc.net/problem/15977 정해는 다차원 세그트리나 이분탐색+set이다. https://codeforces.com/blog/entry/43319 koosaga님의 아이디어를 구현. m=2인 경우 정렬 후 LIS m=3인 경우 정렬 후 LIS on pair (x,y값이 모두 증가하는 형태) 링크의 설명이 너무 명료하므로 큰 그림은 생략. [m+1,e] 범위의 dp를 [s,m] 범위의 dp 값으로 초기화 하는 과정만 기록 세그트리는 y를 인덱스로 하고 dp값을 값으로 갖는다. 1. 하나의 벡터에 {x,y,idx}를 [s,e]범위 모두 넣어준 후 x값 기준으로 정렬한다. 2. idx가 md이하인 경우 세그트리를 업데이트 해준다. 3. idx가 md초과인 경우 세그트리의.. 2020. 5. 30. BOJ 18437 - 회사문화 5 (레이지, ett, 트리) https://www.acmicpc.net/problem/18437 ett+세그(구간업뎃) 최대 1e5개의 정점으로 이뤄진 트리가 주어진다. 각 정점마다 꺼짐,켜짐 두 상태를 지닐 때, 다음 쿼리에 답하라 (초기엔 모두 켜짐) 1 x : x를 조상으로 둔 모든 정점 켬 2 x : x를 조상으로 둔 모든 정점 끔 3 x : x를 제외한 후손 중 켜진 정점들의 수 ett+레이지 하면된다. 세그엔 구간합을 담고, 쿼리마다 x서브트리 모두 켜기/끄기만 유의해서 짜주면 된다. 모두 켜는 연산의 경우 seg[i] 는 해당 구간의 크기 값을 담고, 끄는 경우엔 0을 담으면 된다. 레이지 배열엔 적용할 연산을 담는다고 생각하면 된다. const int MAX = 1e5 + 4; const int SMAX = (1 = .. 2020. 5. 21. BOJ 2568 - 전깃줄2 ( LIS, segtree ) www.acmicpc.net/problem/2568 pair로 입력받아 정렬후 second값의 LIS를 제외한 나머지의 first값 출력 위 점화식을 구간최대 세그트리를 이용해서 구하면 된다. 세그트리의 인덱스는 second값. const int MAX = 1e5 + 4; const int SMAX = (1 1) { i /= 2; seg[i] = max(seg[i * 2], seg[i * 2 + 1]); } } P val(int s, int e, int node, int ns, int ne) { if (e x >> y; a[i] = { x,y }; } sort(a + 1, a + n +.. 2020. 5. 14. 이전 1 2 다음
