Считать количество точек в левом нижнем квадранте?

Question

У меня проблемы с пониманием решения алгоритмической проблемы

В частности, я не понимаю, как или почему эта часть кода

s += a[i];
total += query(s);
update(s);

позволяет вычислить общее количество точек в нижнем левом квадранте каждой точки.

Может кто-нибудь уточнить, пожалуйста?

Answer 1

В качестве аналога для плоской задачи рассмотрим это:

1. Чтобы точка (a, b) находилась в нижнем левом квадранте (x, y), a
2. При выполнении итерации в порядке возрастания все точки, которые рассматривались ранее, лежат слева по сравнению с текущей (i, P[i])
3. Таким образом, нужно только найти все P[j] s меньше, чем P [i], которые рассматривались до сих пор

* текущая точка относится к рассматриваемой точке в текущей итерации цикла for, который вы процитировали, т. е. (i, P[i])

Давайте определим другой массив, C[s]:

C[s] = Number of Prefix Sums of array A[1..(i - 1)] that amount to s

Таким образом, решение для #3 становится суммой... C[-2] + C[-1] + C[0] + C[1] + C[2] ... C[P[i] - 1], то есть префикс суммы C[P[i]]

Используйте BIT для хранения префиксной суммы C, определяя таким образом запрос (ы) как:

query(s) = Number of Prefix Sums of array A[1..(i - 1)] that amount to a value < s

Используя эти определения, s в данном коде дает сумму префикса до текущего индекса i (P[i]). Total создает ответ, а обновление просто добавляет P [i] в ​​BIT.

Мы должны повторить этот метод для всех я, следовательно, для цикла.

PS: он использует структуру данных, называемую двоичным индексированным деревом ( http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees) для операций. Если вы не знакомы с ним, я рекомендую вам проверить ссылку.

РЕДАКТИРОВАТЬ: Вам дан массив S и значение X. Вы можете разбить S на два непересекающихся подмассива так, чтобы в L все элементы S были меньше X, а в H - те, которые больше или равны X.

A: All elements of L are less than all elements of H.

Любая подпоследовательность T в S будет иметь некоторые элементы из L и некоторые элементы из H. Скажем, у нее есть p элементов из L и q из H. Когда T сортируется по T', все p элементов из L появляются перед элементами q Н из-за А.

Median being the central value is the value at location m = (p + q)/2

Интуитивно понятно, что наличие q >= p подразумевает, что медиана лежит в X, в качестве доказательства: значения в положениях [1..p] в T 'принадлежат L. Поэтому для медианы, находящейся в H, ее положение м должно быть больше р:

m > p
(p + q)/2 > p
p + q > 2p
q > p
B: q - p > 0

На компьютере q - p я заменяю все элементы в T 'на -1, если они принадлежат L (= X). T выглядит примерно так: {-1, -1, -1... 1, 1, 1} Это имеет p раз -1 и q раз 1. Сумма T 'теперь даст мне:

Sum = p * (-1) + q * (1)
C: Sum = q - p

Я могу использовать эту информацию, чтобы найти значение в B.

Все подпоследовательности имеют вид {A[i], A[i + 2], A[i + 3] ... A[j + 1]}, так как они являются смежными, чтобы вычислить сумму A [i] в ​​A[j + 1], я могу вычислить сумму префикса A [i] с помощью P[i] = A[1] + A[2] + .. A[i - 1] Сумма подпоследовательности от A [i] до Тогда [j] может быть вычислено как P[j] - P[i] (j больше j и i). Имея в виду C и B, мы заключаем:

Sum = P[j] - P[i] = q - p  (q - p > 0)
P[j] - P[i] > 0
P[j] > P[i]

j> i и P[j] > P[i] для каждого решения, которое дает вам медиану> = X

В итоге:

1. Замените все A [i] на -1, если они меньше X и -1 в противном случае
2. Компьютерные префиксные суммы A [i]
3. Для каждой пары (i, P[i]) подсчитайте пары, которые лежат в его нижнем левом квадранте.