2021년 1월 7일 PS 일지

자기 전까지는 오늘이 맞지~

 

www.commonlounge.com/discussion/f6052177ea3543439251079f57f480e0

 

요기 옛날에 하다가 접었었는데, 초반 문제들이 너무 쉬운게 원인이다. 어려운거부터 해야지

 

보니까 어려운게 없다

ㅋㅋㅋ

엄청 대단한건줄 알았는데 별거 없네.

 

이래서 사람은 어떤거든 시작하고 봐야 한다.

일단 하기로 이미 글을 적어 놨으니, 모르는걸 찾아서 공부한다.

 

 

1. Augmented Segment Tree

코포 링크로 연결된다.

PST 등 모르는 개념이 있어서 함께 공부하기로 한다

 

첨에 세그먼트 트리를 개념을 한 번 읽어봤다. 이미 알고 있는거여서 개쉽네~ 하고 넘기려다가

예제 문제 들어가봤더니.. 어렵네?

이때 이상함을 느끼고 기초부터 다잡고 가기로 했다.

 

한 5분 고민해보고 모르겠어서 원 글로 돌아갔는데 ㅋㅋㅋㅋㅋ 이걸 세그먼트 트리로 하는게 놀랍다.

글을 읽고 나서 이걸 구현해봐야 하나, 말아야 하나 생각이 들었다.

 

일단 나는 이 프로그램을 전부 진행하는게 목표기 때문에, 먼저 모든 thinking and understanding을 하고 나서 구현을 할 것이다.

 

(1) 그냥 세그

380C - Sereja and Brackets

세그는 두 구간을 합치는거에 주목해야 한다.

여기서 두 subsequence를 합치는거기 때문에 

t[x] = t[ x_l] + t[x_r] + min(o[x_l],c[x_r])이라는 개념을 잡았는데

이건 사고력이 반드시 필요한 요소다.

 

KQUERY

음 첨에 문제 밑에 댓글 읽고 스포를 엄청 당했다 ㅋㅋㅋ

온라인? 일단 쿼리가 업뎃이 없기 때문에 온라인 풀이라 하기도 머한데

머지소트트리를 이용하면 O( Q log ^2 N)에 해결할 수 있다

각 구간을 log N개의 구간으로 분리한 다음 이분탐색으로 K 이상의 원소의 개수를 구해준다.

log^2 N 보다는 확실히 작을거 같은데 일단 넉넉잡으면 저 시-복이 나온다.

 

오프라인 풀이는 정말 재밌다.

시복은 O((Q+N) log QN) 

쿼리랑 a[i]를 각각 좌표압축해주고

어떤 ki <= kj에 대해서 a[i] < ki 이면 a[i] < kj이므로 이를 이용해서

정렬된 ki들에 대해 쿼리를 순서대로 처리해주면 된다.

 

b[i] = a[i] 가 k보다 작은가? 를 세그에 집어넣고 열심히 구간합 세그를 돌리자.

투포인터를 이용해 k가 증가함에 따라 b[i]들을 update 해주면 된다

 

다이내믹 세그 쓰면 먼가 온라인으로 될거 같은데 잘 안 떠오른다.

 

(2) 레이지

레이지는 공부를 3번째 하는데 할 때마다 적응이 안된다 ㅋㅋㅋ

글 한 번 읽고 와야지

처음에 배울 때 push에 미심쩍은 부분이 많았다.

언제 push를 하는가... 왜 여기서 하면 맞고 저기서 하면 맞는가

지금도 모르겠다

+ 세그 트리 만들 때 처음부터 1 ~ MAX 값으로 배열을 세팅해두는 타입이 있고

n에 따라 가변적으로 배열을 만드는 타입이(hui, kks 등) 있는데 전자가 매우 편해보인다. 이제부터는 그렇게 짜봐야지.

 

레이지 한 번 짜보고 자야겠다.

www.acmicpc.net/problem/10999

구현이 안 익숙해서 디버깅하는데 오래 걸렸다.

이게 이제 내 정석 구현이다.

일단 push(propagate)할 때 리프노드인지 체크 안해줘도 되는 부분이 너무 좋다.

처음으로 MAX값 미리 설정해봤는데, 정말 편하다!

 

오늘은 레이지까지 공부해보았다~

다음 수업(월)에 이거 푸는게 목표. 테스트라 생각하자

www.spoj.com/problems/POSTERS/

SPOJ.com - Problem POSTERS

다음주에는 Persistence Segment Tree 및 활용에 대해 공부한다.