Codeforces Round 961 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Единственное отличие между простой и сложной версиями заключается в ограничениях на $$$t$$$ и $$$n$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.
Артур проводит урок для своих знаменитых $$$2 n$$$ рыцарей. Как и все другие студенты, они сидят за партами парами, но по привычке по кругу. Рыцарь $$$2 i - 1$$$ сидит за партой с рыцарем $$$2 i$$$.
Каждый рыцарь имеет интеллект, который можно измерить целым числом. Обозначим интеллект $$$i$$$-го рыцаря как $$$a_i$$$. Артур хочет, чтобы максимальная разница в общем интеллекте по всем парам парт была как можно меньше. Более формально, он хочет минимизировать $$$\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$$$.
Однако рыцарский кодекс позволяет менять местами только противоположных рыцарей в круге, т.е. Артур может одновременно выполнять $$$a_i := a_{i + n}$$$, $$$a_{i + n} := a_i$$$ для любого $$$1 \le i \le n$$$. Артур может делать любое количество таких обменов. Какой наилучший результат он может себе обеспечить?
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. За ним следуют описания наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — количество парт.
Вторая строка состоит из $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — значения интеллекта рыцарей.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$100\,000$$$.
Для каждого набора входных данных выведите одну строку, содержащую одно целое число — минимальная разница, которую Артур может достичь.
526 6 4 4110 1731 10 1 10 1 1033 3 4 5 5 451 2 3 4 5 6 7 8 9 10
0 0 0 2 4
В первом наборе входных данных Артур может поменять местами второго и четвертого рыцарей. Тогда общий интеллект на обеих партах составит $$$10$$$.
В третьем наборе входных данных Артур может сделать $$$0$$$ операций, что приведет к общему интеллекту $$$11$$$ за каждой из парт.
В четвертом наборе входных данных Артур может поменять местами рыцарей с индексами $$$2$$$ и $$$5$$$ и достичь разницы $$$2$$$. Можно доказать, что он не может улучшить свой результат дальше.
Название |
---|