[일반] 이거 어케함

[익명(1.233)]

길이 N짜리 정수 배열 A가 있고 Q개의 질문이 들어오는데 각 쿼리에는 l, r, s, e가 주어지고 A[l]...A[r]들 중 s 이상 e 이하의 서로 다른 수의 개수를 세는건데 아무리 생각해도 O(Nsqrt(N)logN)밖에 모르겠다.. 이거 조금 더 빠르게 할 수 있을까

[익명(119.71)]

PST 안에 PST 넣으면 안되나

[익명(120.142)]

쿼리가 오프라인일거같은데

[익명(120.142)]

오프라인 쿼리면 MO's algorithm이라고 해서 nsqrt(n)에 가능함

[익명(120.142)]

온라인이면 딱히 생각은 안나는데 pst로도 힘들듯

[익명(59.13)]

모스쓴다음에 s이상 e이하인거 찾는게 logn걸리는거 아님?

[익명(1.233)]

나도 mo's로 생각했는데 log를 어떻게 떼야할지 모르겠다..

[익명(120.142)]

더 줄이긴 힘들거같은데 n x 제한이 몇임?

[익명(1.233)]

n, q 둘 다 20만

[익명(120.142)]

숫자제한은 10억임?

[익명(1.233)]

숫자는 1이상 n 이하

[익명(49.168)]

일단 s=1, e=N인 문제는 서로 다른 수와 쿼리 1의 방식으로 O(QlogN+NlogN)에 풀 수 있음 i부터 j까지의 숫자만 본다고 생각해보자. N'=i의 개수 + (i+1)의 개수 + ... + j의 개수, Q'=(s<=i, j<=e)인 쿼리 개수라고 할 때, 위의 방식대로 O(Q'logN'+N'logN')에 위의 문제를 풀 수 있음. 이제 분할정복을 할거임 첨에 dnc(1, N)을 호출해 dnc(i, j)를 할 때는 s<=i<=j<=e인 쿼리에 대해서 서다수쿼를 푼 다음에 s<=i<=j<=e가 아닌 쿼리들에 대해서 dnc(i, mid), dnc(mid+1, j)에 적당히 나눠줌 (mid=(i+j/2) 쿼리는 최대 2logN개의 dnc 함수에서 사용되고 N'의 합은 NlogN으로 bound되서 풀림

[익명(49.168)]

대충 O(Qlog^2N+Nlog^2N)에 풀리는 듯

[익명(1.233)]

ㄱㅅㄱㅅ

[익명(120.142)]

이거 근데 쿼리가 왜 2logN개임? [s=1,e=1] [s=2,e=2], [s=3,e=3] ... [s=n,e=n] 쿼리면 어캄?

[익명(1.233)]

세그트리처럼 생각해보면 쿼리 하나당 최대 2logN번만 사용됨

[익명(84.157)]

어디 문제임?

[익명(1.233)]

백준 문제인데 문제 푸는 과정에서 저것만 해결하면 되가지고

[익명(175.113)]

값 변경이 없으면 그냥 머지소트트리 쓰면 됨

[익명(1.233)]

어떻게 해?

[익명(175.113)]

https://justicehui.github.io/medium-algorithm/2020/02/25/merge-sort-tree/
수열과 쿼리 3에서 서로 다른 수니까 벡터 압축하고 [l, r] 사이인 개수는 (l 이상) - (r+1 이상)으로

[익명(175.113)]

아 안되는구나 쿼리 합치기가 어렵네