구사과

(Autoamerican, 1980)

푼지 몇달 된 것도 있고 얼마 전에 푼것도 있다. ONTAK2010. Garden https://www.acmicpc.net/problem/8468 쉽게 생각할 수 있는 아이디어는 N^2개의 행을 잡고, 행 각각에서 교집합을 잡아서 O(N) 루프를 돌리는 것이다. N^3의 끔찍한 시간 복잡도를 가지기에 여기서 포기하기 쉽지만, 놀랍게도 sqrt decomposition을 통해서 큰 차이 없이 N^1.5 정도에 풀 수 있다. 행 R에 대해서, Xi == R을 만족하는 i의 개수가 N^0.5 이상일 경우 heavy row라 하고, 아닐 경우 light row라고 하자. 두가지 방법으로 문제를 해결한다. * 두 행 쌍 중 하나라도 light row일 때를 세주자. light row를 하나 잡고, 고를 수 있는..

https://www.acmicpc.net/problem/1209 최근 CF에 똑같은 문제가 출제되었는데, 짱짱맨 분들이 O(nlgn)에 풀어주신 덕분에 오랜 난제(http://koosaga.myungwoo.kr/110) 가 해결됐다.http://codeforces.com/blog/entry/47094?#comment-315161 단조감소는 생략한다. fi(X) = A[1..i]를 단조증가로 만들면서 Ai