Имеется таблица размера $%10^9 \times 10^9$%, в j-м элементе i-й строки которой стоит минимальное натуральное число, такое, что оно не встречается в j-м столбце выше i-й строки и не встречается в i-й строке левее j-го столбца. Требуется отвечать на запросы суммы всех чисел (по модулю $%10^9+7$%, например), которые не превышают $%k$%, в прямоугольнике $%x1 \leq x \leq x2, y1 \leq y \leq y2$%. В каждом запросе даны числа $%k,x1,x2,y1,y2$%.

задан 22 Май '17 8:56

По-моему, тут условие недоформулировано. Непонятно, что нужно сделать в итоге. Ещё полезно уточнить, рассматривается ли значение 0. По идее, оно должно рассматриваться -- тогда закономерность построения таблицы будет более естественной. Довольно быстро можно сказать, что будет на заданном месте.

(22 Май '17 15:16) falcao

@falcao: только натуральные числа, то есть, в первой строке будут числа от 1 до 10^9. Вторая строка начинается с чисел 2, 1, 4, 3, 6. В итоге нужно предложить эффективный алгоритм для ответа на запросы (сложность - полином от log(N), где N - большая сторона прямоугольника запроса).

(22 Май '17 17:54) fasegfaxs

@falcao, но вообще, если рассматривать 0, то ничего поменяться не должно, все числа сдвинутся на 1.

(22 Май '17 18:09) fasegfaxs
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×242

задан
22 Май '17 8:56

показан
277 раз

обновлен
22 Май '17 18:09

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru