2021년 1월 11일 PS 일지

7 - 성공

8 - 성공

9 - 실패

10 - 실패

 

아무래도 거창한 계획을 세우면 실패하나 보다.

지나간건 잊어버리고 오늘 PS한 걸 적는다. 다시 무계획의 삶으로~

 

www.spoj.com/problems/POSTERS/

SPOJ.com - Problem POSTERS

오늘은 이걸 푸는 것으로 시작했다.

 

ㅇㄴ ㅋㅋㅋㅋ 처음에 엄청 어려운 문젠 줄 알았으나

예전에 이미 풀어본 문제다.

code.sasa.hs.kr/problem.php?id=1317

SASA OJ discuss3

다양한 풀이 중 난 2가지를 안다.

 

Q번 벽을 칠한다. -> L부터 R까지 블럭들을 C의 색으로 칠하기

마지막으로 칠한게 우선순위가 제일 높다.

 

처음 떠올린건 L번부터 R번까지 비재귀 세그 방법을 이용해서 여러 조각으로 나눈 다음 색깔과 우선순위(i번째 칠한거)를 같이 저장하는 거다. 이를 모든 쿼리에 대해 실행해준 다음, 각 조각에 대해 자신을 포함하는 모든 조각을 살펴봐 우선순위가 가장 높은 쿼리의 색을 출력하면 된다. 레이지 세그 전혀 필요 없는데 왜 레이지가 나왔지..?

 

구사과님 방법은 DSU!

노드들을 연결리스트마냥 구성한다.

nxt[1] =2, nxt[2] = 3, ... nxt[n-1] = n 이런식으로

paint쿼리를 거꾸로 처리하는데 가장 마지막에 들어온 쿼리의 결과를 유지시키기 위함이다.

int paint(int s, int e, int x){
    if(!ret[s]) ret[s] = x;
    if(s >= e) return s;
    return nxt[s] = paint(nxt[s],e,x);
}

이렇게 각 벽의 색과 nxt를 갱신시켜준다.

amortized O(N)에 모든 쿼리가 완료된다.

이미 벽이 색칠되어 있을 경우 그 부분은 O(1) 만에 건너 띄어지기 떄문이다.

이 방법을 어떻게 생각해냈을까?

 

사실 POSTERS과 

좌표압축 + DSU / Segment Tree로 적은 메모리를 사용해 문제를 해결할 수 있다.

 

그렇다면 Lazy Propagation을 사용하는 풀이는??

오직 레이지를 적용시킬 수 있다는 가능성에만 의미를 두자.

그냥 쿼리 순서대로 가면서 값 할당 레이지 업데이트를 수행한다.

신기한 것은 tree 배열 없이 lazy 배열만으로 모든 쿼리를 처리할 수 있다.

 

 마지막에 포스터 수 개수 처리하는게 특이하다.

O(n log k)에 처리하는데 만약 레이지 값이 있으면 포스터의 색을 set에 넣는다.

이게 최악의 경우 O(n)개의 노드로 분기되고 set에 최대 k개를 집어 넣을 수 있으므로 O(n log k)의 시간복잡도가 나온다.

온라인 쿼리기는 하나 딱히 온라인 쿼리로서 의미가 없는게,

개수 세는 쿼리가 O(n log k) 다. 오프라인보다 이점이 없는 문제.

 

백준 문제는 [l,r]의 범위가 [0,10^8]이기 때문에 강제로 좌표압축을 적용해야 한다. 

지금까지 소개한 풀이는 전부 플레급은 되는데 어떻게 골드 3을 받았는지는 모르겠다.

 

왜 티어가 그렇게 됐는지 보니... n이 10000이기 때문에 좌표압축 + O(N^2) 알고리즘이 통과한다. 느슨한 시간 제한이 좋은 문제를 망쳐놨다.

 

계획 상 Persistence로 넘어가는게 맞으나, 원 글의 흐름을 조금 더 따라가 보도록 하겠다.

 

Segment Tree with Vectors

 KQUERYO

 

2021년 1월 7일 PS 일지에서 소개했던 K-Query문제의 온라인 버전이다.

 

역시 Merge Sort Tree를 이용하면 온라인에 O(n log^2 n 에 해결할 수 있다.)

퍼시스턴트 세그트리 연습문제라는 말도 있으니 퍼시를 공부하고 조금 있다 돌아와보자.

 

mergesort를 구현할 때 이미 내장함수가 있어서 한 줄로 구현할 수 있다!!

#define all(v) v.begin(),v.end() 

Merge Sort Tree가 왜 성립하는가? 하면

n

n/2 n/2

n/4 n/4 n/4 n/4

. . . 

 

이런 식으로 log n의 높이를 가지는 트리의 각 층의 개수가 n으로 일정하기 때문이다.

총 노드의 개수는 O(n log n)이므로 공간이 충분하다.

 

Segment Tree에는

Set, Trie, Segment Tree, Fenwick Tree, DSU 등이 들어갈 수 있다.

 

코드업 3180 간단한 문제

codeup.kr/problem.php?id=3180

간단한 문제

세그에다가 맵 박아서 푸려고 시도했다. GCC Optimze, fastio 등 최적화 시도는 번번히 무산되고... 맵은 정말 느리다는 결론을 내렸다.

 

여담으로 이 문제는 평방분할으로 쿼리 당 O(sqrt N)에 해결 가능하다. 또는 gnu pbds ordered set으로 쿼리당  O(logN)에 해결 가능하다.

 

알고리즘 빡공방(카카오 옾챗)에 질문 올렸는데 갓갓 AM님이 좌표압축 + 동적세그로 쿼리 당 O(log N)에 가능하다고 말씀해주셨다.) God.. 동적 세그 구현에 현재 자신이 없기 때문에 하던거 마저 하고 짜봐야 겠다.

 

*여담으로 AM님의 God력은 예전에 이 설명을 들었을 때도 느꼈다.

 

< 1<=L<=R<=10^9 , L부터 R 사이에 있는 정수(경계 포함) 중 소수의 개수 구하기 >

[AM] [5:26 AM] 먼저, 에라토스테네스의 체로 sqrt(10^9)=31622까지의 소수를 구해놓는다면 [a, a+10^6) 구간의 소수의 개수를 10^6 log log 31622 정도에 알수있어요
[AM] [5:30 AM] [1, 10^6], [10^6+1, 2*10^6], ..., [999*10^6+1, 10^9] 10^6길이 단위의 구간이 1000개 있으니 위의 방법을 사용하고, 100만칸짜리 배열을 초기화하고, 다시 사용하고, ... 1000번을 반복하면 되네요 ㅈㅅ 느리네요
[앵귤러를 보면 울리는 사이렌] [5:30 AM] ...빠를거같은데?
[weasell] [5:30 AM] 이게 제일 빠른것같네요
[AM] [5:31 AM] 백준에서 1<=L<=R<=10^9인 [L, R]구간의 소수개수를 세는 문제가 나왔다면 저 1000칸을 DB처리해서 0.1초안에 맞을수있는데

 

여담으로 세그의 각 노드에 좌표압축을 박아서 O(N log^2 N)에 해결할 수 있다.

먼저 모든 쿼리를 받은 다음 각 인덱스마다 vector를 만들어 한 번이라도 등장하는 원소들을 모두 카운팅 해준다.

Merge Sort Tree를 구축한다. 각 노드의 vector을 unique함수를 이용해 set으로 만들어준다.

amortized하게 공간복잡도는 O( (Q+N) log N )이다.

 

쿼리가 들어오면 세그를 돌린다.

업데이트 -> 각 노드 별로 vector에서 lower_bound 돌려서 인덱스에 대응하는 cnt ++ (기존 원소 cnt --)

개수 쿼리 -> 각 노드 별로 vector에서 lower_bound 돌려서 인덱스에 대응하는 cnt 출력

 

이렇게 해서 O(N log^2 N)에 해결 가능하다.

코드

 

cnt 배열을 만드는게 아니라 펜윅을 박으면 Ai ... Ar 중 k보다 작은 원소의 개수를 구할 수도 있다.

www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray-set-2-including-updates/

Number of elements less than or equal to a given number in a given subarray | Set 2 (Including Updates) - GeeksforGeeks

이 Article에서는 평방 분할 을 통해 문제를 O(Q log N sqrt N)에 해결했는데

위 방법을 이용하면 O(Q log^2 N)에 해결할 수 있다.

 

 

codeforces.com/gym/100513/problem/C

Problem - C - Codeforces

이 문제 꽤 오랫동안 고민했는데 못 풀었다. 목요일날 테스트 문제는 이거다.

 

codeforces.com/contest/396/problem/C

Problem - C - Codeforces

얘도 어렵다...

 

Segment Tree는 풀어도 풀어도 재밌는 문제들이 정말 많다.

 

PST는 목요일날 하자 !ㅋㅋ

 

www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

책 읽다가 갑자기 끌려서 가가두점 문제를 공부했다.

1. 스위핑 구현 방법( 분할정복은 기존에 알고 있었다.) 스위핑이 분할정복보다 훨씬 쉬움!

2. 작동 원리 -> 지금까지 구한 d보다 거리가 작은 점은 최대 6개

 

굉장히 중요한 사실을 알아 냈는데

std::lower_bound와

std::set::lower_bound는 다르다!!!

 

lower_bound(s.begin(),s.end(), value) 이거 쓰면 정말 큰일난다.

lower_bound는 random - access - iterator을 가진 자료구조에만 log (N)에 작동하기 때문이다. set은 무작위 접근이 안되므로 O(N)에 lower_bound가 동작한다. set에서 이분탐색을 쓰려면 

꼭! set의 내장함수 lower/upper bound를 사용해야 한다. 레퍼런스

정말 중요한 사실이니 꼭 기억하자.