Условия легко сводятся к таким: Дано число 1 ≤ n ≤ 10⁵ и n целых чисел 1 ≤ a_i ≤ n,

Нужно разбить их на две группы с одинаковой суммой и вывести разбиение или сказать, что это невозможно.

Условия очень похожи на рюкзак, но я умею решать эту задачу только жадно. В разборе написано, что задачу можно решить каким-то рюкзаком за .

Линк на Разбор и на Условия (задача C)

Надеюсь, вы поможете мне решить эту задачу. :]

I mean proven things like comparison sort can't have an asymptotic better than N * log(N). I haven't ever heard about other similar cases. Is there anyone who knows?

UPD: probably I did not describe the question properly enough, although zxqfl gave an answer I expected to get. I have meant that we have some sort of problem with strict restrictions, for example finding a minimal path from S to T in a graph with 1 ≤ w(e) ≤ 10⁹ integer length of all edges and this is proven that this task can not be solved faster than in O(M * logN) or something like that. (Not exactly saying I know how to prove this, just giving an example)

Дан массив V целых чисел.

Нужно обрабатывать следующие два типа запросов

1. Запрос содержит L, R, A, B, требуется посчитать, сколько таких j, что A ≤ j ≤ B и L ≤ V_j ≤ R

2. Запрос содержит i и X, $V_i = $

Один человек сказал мне, что это невозможно решить с асимптотикой O(log n) на запрос.

Правда ли это? Будет неплохо увидеть доказательство того, что это правда или решение, если это утверждение неверно.

(Также мне были интересны другие асимптотики, которые могут быть лучше чем O(log² n).) Решение за O(log n * log max) тоже вполне очевидное решение (max — максимальное число, которое может быть в массиве V)