백준 7578 공장

https://www.acmicpc.net/problem/7578

7578번: 공장

예제 그림을 보면 교차하는 부분은 3곳

교차하는 지점의 특징: 똑같은 132가 있어도 A에서의 위치와 B에서의 위치가 다르다

A[i]를 A에서 i의 위치, B[i]를 B에서 i의 위치라고 치면,

A[i]<A[j]

B[i]>B[j]

조건이 성립하면 접점 1개가 생긴다고 할 수 있다

 

그냥 반복문으로 단순 구현하면

A를 i로 돌면서 j로 조건에 맞는 수가 있는지 찾는 2중for문이 되고

O(n^2)의 시간복잡도로 5000000^2하고 터진다

 

어차피 교차를 세면 되니까

A[i]를 앞에서부터 보면서 처리하면 자연스럽게 A[i]<A[j]를 만족함

tree[i]: A[i], B[i]가 처리되었으면 1, 아니면 0을 넣는 트리 라고 하면

B[i]>B[j]는 트리에서 A[i]범위에 대한 개수를 세는 방식으로 해

 

i	1	2	3	4	5
B[i]	392	351	132	311	231
tree[i]	0	0	0	0	0

A[i]에서 132를 보면

A 132앞에는 아무것도 없고, B 132뒤에는 311, 231이 있지만 트리기준 311~231의 합은 0이므로

132와 교차하는 부분은 없다고 알 수 있고(현재 기준)

132를 처리했으니 B에서 132에 해당되는 3번 인덱스에 처리했다는 의미의 1을 넣는다

 

i	1	2	3	4	5
B[i]	392	351	132	311	231
tree[i]	0	0	1	0	0

A에서 392를 보면

B에서 392 뒤에는 351~231까지 4개 수가 있고,

tree[2]~tree[5]를 다 더하면 1이므로 겹치는 부분이 1개 있다고 할 수 있다

정답에 +1을 추가하고 392를 처리했으니 tree[1]에 1로 해준다

 

i	1	2	3	4	5
B[i]	392	351	132	311	231
tree[i]	1	0	1	0	0

A에서 311을 보면 B에서 311 뒤에는 231밖에 없고

tree기준 231~231의 합은 0이므로 정답+0, 4번에 +1해준다

 

i	1	2	3	4	5
B[i]	392	351	132	311	231
tree[i]	1	0	1	1	0

A에서 351을 보면 B에서 351 뒤에는 132~231이 있고

tree기준 132~231은 tree[3]~tree[5]의 합은 2이므로 겹치는 부분이 2개라는 의미다

정답에 +2를 해주고 351을 1로 바꾼다

i	1	2	3	4	5
B[i]	392	351	132	311	231
tree[i]	1	1	1	1	0

A에서 231을 보면 B에서 231 뒤에는 아무 것도 없으므로 정답 +0이고

231 처리했으니까 tree[5]를 1로 갱신하고 끝

 

tree[i] 구간의 합을 구할 때 시간 단축을 위해 세그트리가 들어가기 때문에 세그먼트 트리 문제가 된다

근데 합을 구하는 경우에는 펜윅트리가 더 빠르기 때문에 펜윅트리를 썼다

 

코드1

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/7578%20%EA%B3%B5%EC%9E%A5_1.cpp

 

코드2

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/7578%20%EA%B3%B5%EC%9E%A5_2.cpp