A는 최대 1 개의 정수를 포함하는 배열입니다.범위의 정수의 정리
log (N) 복잡도에서이 배열에 대해 2 가지 연산을 수행해야합니다 (여기서 N = A의 수는입니다).
조작 1 소정 V, I, J 우리 A [K](I < < = K = J)에 V를 추가 할 수있다. 난 & J 계산 (A [i가 * A [i가 + 1] * A [i가 + 2] * ... * A [J]) %의 M 주어진
동작 2, . (M은 소수이며 모든 작업에서 동일합니다.)
거의 10 의 작업이 수행됩니다.
log (N)에서 불가능한 경우 작업을 수행하는 데있어 가능한 최상의 복잡성은 무엇입니까?
당신이 범위 [i, j]의 모든 요소에 액세스해야 할 것 같습니다 이후는 복잡
음, 첫 번째 연산은 몇 가지 데이터 구조를 사용하여 log (K) 복잡도에서 수행 할 수 있습니다. 여기서 K는 해당 범위의 선형 크기입니다. 두 번째 작업은 데이터 구조 기술을 사용하여 동일한 복잡성에서 수행 할 수 있습니다. –
그런 다음 모든 요소에 액세스하지 않고이를 수행하는 방법을 찾으십시오. : P –
@DennisMeng - 분명히 그렇게하려고 노력하지만 그렇게 할 수 없다면 불가능하다는 것을 증명하지 못합니다. – IVlad
그것은 지는 N의 순서에있을 가능성이, 당신은했습니다, 그 범위의 선형 크기에 따라 달라집니다 각각을 바꾸어야합니다. 바울은 O (N)보다 모든 알고리즘을 더 빠르게 만들 수 없다고 말했습니다. K는 문제의 매개 변수가 아니며 단지 변수 일뿐입니다. 따라서 Bidhan의 대답에서 log (K)는 의미가 없습니다.
이제는 문제가 적절한 시간 복잡성이 아니라 대규모 병렬 작업 트리의 높이 (예 : CUDA를 사용하는 경우와 같은)에 대한 질문이 충분하다면 충분한 스레드가 있으면 작업이 자주 수행됩니다 모든 연산의 독립성 때문에 O (1)에서 1, O (log (N))에서 연산 2는 인접 요소의 mod M 쌍 (100000/2 스레드 필요)을 곱한 다음 인접한 결과 쌍 등을 대답에 도달했습니다.
그러나 이것은 문제가되지 않았습니다. 대용량 병렬 컴퓨팅을 제외하면 각 연산의 복잡성은 O (N)입니다.
"각자 변경해야합니다"는 따르지 않습니다. 'O (N)'보다 더 빠르다고해도 (의심 스럽지만) 이것은 증명이 아닙니다. 각 항목을 반드시 변경할 필요는 없으며 변경된 사실에 관한 특정 정보를 저장하고 여전히 운영 2 쿼리에 응답 할 수 있습니다. – IVlad
예, ** IVIad **에서 말했듯이 답을 계산하려면 모든 요소에 액세스 할 필요가 없습니다. 그리고 로그 (K)는 세그먼트 트리에 대한 지식이있는 사람에게 완벽합니다. –
작업 1의 경우 '추가 v'또는 'v 곱하기'를 실제로 의미합니까? 'v 곱하기'의 경우, 내 솔루션을보다 쉽게 적용 할 수 있습니다. 세그먼트 나무가 'O (log N)'솔루션의 실행 가능한 옵션이라고 생각하지만 지금까지는 운영 1을 수행하는 방법을 알지 못합니다. spoj로 태그를 지정했는데 spoj 문제에 연결할 수 있습니까? – IVlad
@IVlad 또한 ** ** **로 번식하는 것은 세그먼트 트리 또는 이진 인덱싱 된 트리로 수행 할 수 있음을 알았습니다. 이것은 특정 spoj 문제가 아니지만, 그 트릭을 알고 spoj에서 여러 가지 문제를 해결하는 데 도움이됩니다. –
이 작업을 시도 중입니다. 나는 또한 sublinear가 가능하다는 것을 확신하고있다. 나는 아직 문제를 완전히 해결하지 못했지만, (0부터 M-1까지의 정수, M을 덧셈에 덧셈, M을 곱셈하는 곱셈,) 필드를 형성합니다. –