뉴비의 PS 낙서장

Mo's algorithm 을 사용하는 문제다. 와아아아아아아앙 짝짝짝짝 각 숫자마다 list로 관리하면서 (dq[i].front-dq[i].back) 의 값이 숫자 i 의 최대 길이이다. 이제 이 숫자 i의 최대길이를 O(k) 가 아닌 O(sqrt(K)) 에 구해아 한다. 이 방법은 최대길이를 관리하는 버킷을 만들어서 sqrt(K) 개로 쪼갠다음 각 구간을 관리한다. 이러면 제일긴 길이 를 찾는방법을 O(sqrt(K)) 만에 구할 수 있다. 자세한건 코드를 보자. #include using namespace std; list dq[300005]; int n,k,Q,val,sz; int ans[300005],a[300005]; int b[300005],cnt[5000005]; struct Query { ..