솔브드 플레찍기 2일차-12015, 12738, 7578, 3654, 18436

오늘은 세그트리 달린다

https://www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

 

최대/최소값 찾기

12015 가장 긴 증가하는 부분 수열2

tree[i] = 수 A[i]를 마지막으로 하는 LIS의 길이로 두면,

1) i보다 앞에 있으면서(j<i)

2) i보다 작은 수(A[j] <A[i])

인 j중에 가장 긴 LIS 길이를 찾고

A[i]인 자기 자신의 길이+1해주는 식으로 tree를 채운다

 

1, 2번 조건을 만족하려면 [1, A[i]-1]범위 안에 있으면 되고

그 범위 안의 LIS 길이의 최대+1 을 tree[i]에 갱신

 

예를 들어 아래와 같은 A[i]와 tree[i]가 있을 때

i	1	2	3	4	5	6	7
A[i]	1	3	2	4	3	4	2

i	1	2	3	4	5
tree[i]	0	0	0	0	0

A[i]에서 1을 보면, [1, A[i]-1]범위는 [1,0]이고

tree[1,0]의 최대값은 0이므로 0에다가 본인 1자리 포함해서

여기까지의 최대 LIS길이는 1이라는 의미로 tree[i]배열에 1번칸 1로 갱신

 

i	1	2	3	4	5	6	7
A[i]	1	3	2	4	3	4	2

i	1	2	3	4	5
tree[i]	1	0	0	0	0

A[2]는 3이고 볼 범위는 [1,2]

tree[1]에 1이 있으니까 LIS는 1이고 tree[3]에다가 본인 포함해서 2를 넣는다

 

이런 식으로 하다 보면 최종 tree배열

i	1	2	3	4	5
tree[i]	1	2	3	4	0

 

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/12015%20%EA%B0%80%EC%9E%A5%20%EA%B8%B4%20%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B42.cpp

 

 

12738 가장 긴 증가하는 부분 수열3

2번이랑 똑같은데 범위가 커졌다

2번은 1<=N<=1백만, 1<=A[i]<=1백만 인데

tree[i]는 수i를 마지막으로 하는 이라서 M까지만 도니까 NlogM으로 가능했음

근데 3번은 범위가 20억이라 세그트리가 안 돌아감

 

범위를 줄일 수 있는 방법은

이 문제에서 구해야 하는 LIS는 '가장 긴 증가하는 부분 수열'이라서

값 자체는 무슨 값이든 상관없다는 점을 가지고 생각해 볼 수 있음

 

만약에 2, 50, 25, 20, 35, 60, 20, 50, 35, 3, 8, 25라는 수가 있다면

중복을 제외하고 2, 50, 25, 20, 35, 60, 3, 8 만 남긴 후

앞에서부터 1, 2, 3, 4..로 치환해준다

그리고 다시 처음의 수들을 바꿔주면

1, 7, 5, 4, 6, 8, 4, 7, 6, 2, 3, 5가 되고

이 수에서 LIS를 구해도 같은 정답이 나오게 된다

이렇게 수의 범위를 줄여서 1~N범위로 만드는 것을 좌표압축이라고 함

 

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/12738%20%EA%B0%80%EC%9E%A5%20%EA%B8%B4%20%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B43.cpp

 

합 구하기

7578 공장

https://foxtrotin.tistory.com/164

백준 7578 공장

3654 영화수집

1) DVD를 빼서 맨 위에 올린 뒤에 있던 자리를 굳이 채울 필요가 없다

2) DVD 표지에 붙어있는 숫자는 필요없다 그냥 DVD 1개라는 것만 의미가 있음

 

DVD가 있다는 의미로 해당 부분에 tree[i]를 1로 채우고

DVD를 뺄 때마다 그 자리~맨 위까지 다 더한다(펜윅트리)

그러면 어차피 다 1이니까 DVD의 수가 나옴

뺀 자리는 그냥 0으로 놔두면 +0이니까 상관없음

 

코드1

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/3653%20%EC%98%81%ED%99%94%20%EC%88%98%EC%A7%91_2.cpp

 

코드2

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/3653%20%EC%98%81%ED%99%94%20%EC%88%98%EC%A7%91(%ED%8E%9C%EC%9C%85%ED%8A%B8%EB%A6%AC).cpp

 

 

18436 수열과 쿼리37

짝수의 개수, 홀수의 개수를 출력->수는 중요하지 않다 짝/홀만 중요함

tree[i]=A[i]가 짝수면 1, 아니면 0 (반대도 상관없음)

 

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/18436%20%EC%88%98%EC%97%B4%EA%B3%BC%20%EC%BF%BC%EB%A6%AC37.cpp