Начнём с $$$p = [1, 2, 3, \dots, n]$$$. Для этой $$$p$$$ значение $$$f(p) = 0$$$.

Будем перемещать $$$n$$$ в начало по одной позиции за раз. Легко заметить, что на каждом шаге значение функции увеличивается на $$$2$$$.

Теперь переместим $$$n - 1$$$ на вторую позицию, затем $$$n - 2$$$ на третью и так далее, пока не получим $$$p = [n, n - 1, \dots, 2, 1]$$$. Для этой перестановки $$$f(p) = \lfloor \frac{n^2}{2} \rfloor$$$.

В процессе мы получили все чётные значения от $$$0$$$ до $$$\lfloor \frac{n^2}{2} \rfloor$$$, поскольку на каждом шаге прибавляли по $$$+2$$$.

Докажем, что другие значения получить невозможно.

Во-первых, очевидно, что нельзя получить значение меньше $$$0$$$ или больше $$$\lfloor \frac{n^2}{2} \rfloor$$$.

Во-вторых, мы можем получить только чётные значения, потому что каждый свап двух элементов изменяет значение функции на чётное число.

Получаем ответ: $$$\lfloor \frac{n^2}{4} \rfloor + 1$$$.

Сложность: $$$\text{O}(1)$$$.

#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
#define SPEEDY std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
#define forn(i, n) for (ll i = 0; i < ll(n); ++i)

void solution(){
    ll n;cin>>n;
    ll k=n/2;
    if (n%2){cout<<k*(k+1)+1;return;}
    cout<<k*k+1;
}

int main() {
    SPEEDY;
    int t; cin>>t;
    while (t--){
        solution();
        cout << '\n';
    } return 0;
}

Пусть $$$x \gt 1$$$, обозначим за $$$c$$$ количество единичных битов в его двоичной записи. Ясно, что при $$$n \le c$$$ нам будет выгодно просто раскидать по элементам массива разные степени двойки, в результате получив минимально достижимую сумму $$$x$$$. Если же $$$n \gt c$$$, то нам очевидно будет выгодно добавить в лишние $$$n-c$$$ элементов только единицы, при этом в случае, если $$$n-c$$$ нечётно, нам придется также добавить дополнительную единицу в один из $$$c$$$ блоков со степенями двойки, чтобы $$$\text{XOR}$$$ всех единиц стал равен $$$x$$$ $$$\text{mod}$$$ $$$2$$$.

Если $$$x=1$$$, то при нечетном $$$n$$$ мы очевидно просто заполним все элементы массива единицами, в противном случае нам потребуется использовать пару $$$[2, 3]$$$, $$$\text{XOR}$$$ которой равен $$$1$$$, получив наименьший счёт $$$n+3$$$.

В оставшемся случае с $$$x=0$$$ ситуация почти идентична предыдущей с тем исключением, что не существует подходящего примера для $$$n=1$$$ (и этот случай является единственным, имеющим ответ $$$-1$$$), то есть для чётного $$$n$$$ ответом будет само $$$n$$$, а иначе — $$$n+3$$$ (так как мы используем тройку $$$1 \oplus 2 \oplus 3 = 0$$$).

Асимптотика $$$\text{O}(1)$$$ на тест.

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

void solution(){
    int n,x;cin>>n>>x;
    int bits=__builtin_popcountll(x);
    if (n<=bits){cout<<x;return;}
    if ((n-bits)%2==0)cout<<x+n-bits;
    else{
        if (x>1){cout<<x+n-bits+1;return;}
        if (x==1){cout<<n+3;return;}
        else{
            if (n==1){cout<<-1;return;}
            else cout<<n+3;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1; 
    cin>>t;
    while (t--){
        solution();
        cout << '\n';
    } return 0;
}

Заметим, что подряд идущие кнопки с одинаковым весом не влияют на ответ, поэтому для такой последовательности кнопок оставим только одну из них.

В получившемся массиве находим пики (локальные максимумы — элементы, которые строго больше обоих соседей). Количество таких пиков и является ответом, так как:

• Каждый пик отделен от других более маленькими элементами. Поэтому попасть в пик можно только создав клона в нём.

• Если были в кнопке, можем в нее вернуться.

• В любой элемент кроме пиков гарантированно можно попасть из большего соседа, так как мы уже посещали его. Поэтому создание клонов во всех остальных элементах не требуется

Сложность: $$$\text{O}(n)$$$

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int tt = 1;
    cin >> tt;
    while(tt--){
        int n; cin >> n;
        vector<int> a;
        a.push_back(-1e9);
        for (int i = 0; i < n; i++){
            int x; cin >> x;
            if (a.back() == x);
            else a.push_back(x);
        }
        a.push_back(-1e9);
        
        int ans = 0;
        for (int i = 1; i < a.size() - 1; i++) 
            if (a[i - 1] < a[i] && a[i] > a[i + 1]) ans++;
 
        cout << ans << endl;
    }
}

Пусть $$$k = 4$$$ и загадан массив:

[  2   4   3   1   2   4   3   1   2   1   3   2   4   1   3   2   4   1  ]

Для наглядности разобьём его на группы по $$$k$$$ элементов:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]

По условию, длины левой и правой частей как минимум $$$k$$$. Запросим левые $$$k$$$ и правые $$$k$$$ элементов. Будем отмечать красным все элементы левого массива, а синим — все элементы правого:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]

Дополним наш массив двумя числами справа (для наглядности перестановок):

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Мы получили перестановки в "нормированном" виде: $$$[2, 4, 3, 1]$$$ и $$$[4, 1, 3, 2]$$$. Возьмём любую позицию, на которой элементы в перестановках различаются. Пусть это будет вторая позиция. Отметим все элементы на выбранных позициях в загаданном массиве:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Среди них находим граничные элементы бинарным поиском за $$$\log \frac{n}{k}$$$ запросов:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Далее рассмотрим отрезок между этими граничными элементами:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Нам не интересны позиции, которые совпадают в обоих перестановках (в нашем случае это только третья позиция). Отбросим элементы на этих позициях:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Среди рассматриваемых элементов бинарным поиском находим граничные за $$$\log k$$$ запросов:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]

Если между граничными элементами есть "ничейные", то однозначного решения не существует и выводим $$$-1$$$. В нашем случае таких элеметов нет, задача решена:

[  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]

Итоговая сложность: $$$2k + \log \frac{n}{k} + \log k$$$ запросов.

#include <cstdio>
#include <cstdlib>
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
typedef long long l;

l a[55], b[55], ui[55];

l ask(l v) {
    printf("? %lld\n", v + 1);
    fflush(stdout);
    l t; scanf("%lld", &t);
    return t;
}

void noans() {
    printf("! -1\n");
    fflush(stdout);
}

void ans(l a, l b) {
    printf("! %lld %lld\n", a, b);
    fflush(stdout);
}

void solve() {
    l n, k; scanf("%lld %lld", &n, &k);

    for (l i = 0; i < k; ++i) a[i] = ask(i);
    for (l i = n - k; i < n; ++i) b[i % k] = ask(i);
	
    l uc = 0;
    for (l i = 0; i < k; ++i) if (a[i] != b[i]) ui[uc++] = i;
    
    if (!uc) {
        if (n == k * 2) ans(k, k);
        else noans();
        return;
    }
    
    l le = ui[0], ri = ui[0] + (n - 1) / k * k;
    while (le + k != ri) {
        l mid = le + (ri - le) / k / 2 * k;
        if (ask(mid) == a[ui[0]]) le = mid;
        else ri = mid;
    }
    
    l lee = 0, rii = uc;
    while (lee + 1 != rii) {
        l mid = (lee + rii) / 2;
        if (ask(le - ui[0] + ui[mid]) == a[ui[mid]]) lee = mid;
        else rii = mid;
    }
    
    l pos1 = MAX(le - ui[0] + ui[lee], k - 1);
    l pos2 = MIN(le - ui[0] + ((rii == uc) ? (ui[0] + k) : ui[rii]), n - k);
    
    if (pos1 + 1 != pos2) { noans(); return; }
    ans(pos2, n - pos2);
}

int main() {
    l t; scanf("%lld", &t);
    while (t--) solve();
}

Предположим, что мы уже удалили одно из рёбер из исходного дерева, тогда у нас осталось какое-то дерево на чётном числе вершин $$$n - 1$$$. Заметим, что максимальная возможная сумма расстояний между одноцветными шариками в нём будет достигаться в том случае, если для каждого из его рёбер все вершины его поддерева наименьшего размера будут разных цветов, поскольку тогда оно будет учитываться в ответе максимальное для него число раз, то есть $$$\min(a, b)$$$, где $$$a$$$ и $$$b$$$ — размеры поддеревьев, связанных этим ребром, ведь пройти больше путей через это ребро, очевидно, не может.
Супер, а давайте тогда подвесим наше дерево за его центроид — вершину, разделяющую дерево на поддеревья, размер которых не превышает половину его размера. Можно доказать, что такая вершина существует в любом дереве (если же их две, то подвесим за любую из них).
Теперь разделим вершины на группы по принадлежности к поддеревьям детей центроида, добавив сам центроид в группу наименьшего размера. Заметим, что размеры всех групп всё ещё не превосходят $$$\frac{n - 1}{2}$$$, а значит, мы можем разбить их на пары таким образом, чтобы в каждой паре обе вершины были в разных группах. Это можно сделать жадно с использованием кучи за $$$O(n \log n)$$$ либо запустив DFS из центроида и раскрашивая вершины в цвета по модулю $$$\frac{n - 1}{2}$$$ (очевидно, что при таком подходе ни в одной группе не окажется двух вершин одного цвета) со сложностью $$$O(n)$$$.
Таким образом, нам остаётся лишь понять, при удалении какого из рёбер значение суммы размеров минимальных поддеревьев по всем рёбрам исходного дерева уменьшится наименее всего. Заметим, что поскольку в начале дерево состоит из нечётного числа вершин, его центроид определяется однозначно и не изменится при удалении любого из рёбер. В то же время, поскольку все пути проходят через центроид, сумму их длин можно переписать как сумму расстояний до центроида. Тогда сделаем два утверждения:

1. Удалить лист выгоднее, чем что-то другое;
2. Среди всех листов наиболее выгодно удалить лист, ближайший к центроиду.

Второе утверждение моментально следует из первого и замечания выше, поэтому нас интересует только первое. Однако это довольно очевидно, поскольку при удалении ребра, помимо вычитания глубины его ближайшей вершины, на один уменьшатся глубины всех вершин в его поддереве, откуда всегда выгоднее будет удалять более глубокие рёбра, чем менее глубокие.
В итоге, с поиском центроида за $$$O(n)$$$ получаем асимптотику $$$O(n \log n)$$$ (при использовании кучи) или $$$O(n)$$$.

#include <cstdio>
#include <vector>

#define S 200005

using namespace std;
typedef long long l;

l coloring[S], centroid, best, best_dist, n, color;
vector<vector<l>> g;

l search_centroid(l u, l from) {
  l sum = 0;
  bool f = true;
  for (l v : g[u]) if (v != from) {
    l t = search_centroid(v, u);
    if (t > n / 2) f = false;
    sum += t;
  }
  
  if (f && n - 1 - sum <= n / 2) centroid = u;
  return sum + 1;
}

void make_coloring(l u, l from, l dist) {
  coloring[u] = (color++) % (n / 2) + 1;
  if (g[u].size() == 1 && dist < best_dist) {
    best_dist = dist;
    best = u;
  }
  for (l v : g[u]) if (v != from)
    make_coloring(v, u, dist + 1);
}

void solve() {
  centroid = -1, best_dist = S, color = 0;
  scanf("%lld", &n);
  g.assign(n, vector<l>());
  for (l i = 0; i < n - 1; ++i) {
    l u, v; scanf("%lld %lld", &u, &v); --u, --v;
    g[u].push_back(v); g[v].push_back(u);
  }
  
  search_centroid(1543 % n, -1);
  make_coloring(centroid, -1, 0);
  
  l bbest = max(best, g[best][0]);
  coloring[centroid] = coloring[bbest];
  coloring[bbest] = 0;
  
  printf("%lld %lld\n", best + 1, g[best][0] + 1);
  for (l i = 0; i < n; ++i) {
    if (i) printf(" ");
    printf("%lld", coloring[i]);
  }
  printf("\n");
}

int main() {
  l tc; scanf("%lld", &tc);
  while (tc--) solve();
}

Можно показать, что для любого массива $$$A$$$, который мы получим в итоге после обрушения всех $$$n$$$ башен, мы также можем получить в итоге любой другой массив $$$B$$$, элементы которого не превышают элементы $$$A$$$. Строгое формальное доказательство приведено в спойлере ниже, здесь будет краткое. Пусть на $$$i$$$-ю башню упало $$$k$$$ блоков за всё время. Тогда, чтобы её высота в итоговом массиве была равна $$$A_i$$$, то $$$A_i$$$ блоков должны упасть после её обрушения, а остальные $$$k - A_i$$$ блоков — до. Тогда мы всегда можем поменять порядок падения башен таким образом, чтобы её высота была равна $$$B_i \leq A_i$$$. То есть мы сделаем так, чтобы $$$B_i$$$ башен упали на башню $$$i$$$ после её обрушения, а $$$k - B_i$$$ — до.

Из этого утверждения о возможности получить меньший массив следует два факта:

1. Для любого ответа $$$\text{MEX} = x$$$ мы также можем получить ответ $$$x - 1$$$. Значит, мы можем применить бинарный поиск по ответу.

2. Для любого ответа $$$\text{MEX} = x$$$ мы можем получить его в виде $$$[0, 0, 0, 0, \ldots, 1, 2, 3, \ldots, x - 1]$$$. Значит, на каждой итерации бинарного поиска по ответу нам нужно проверить возможность получения такого массива. Для этого пройдёмся слева направо по башням, отслеживая количество кубиков, которые в какой-то момент на неё упадут и обрушая каждую башню после требуемого количества кубиков, упавших на неё. Отслеживать количество кубиков оптимальнее всего с помощью метода scanline.

Всего у нас $$$\text{O}(\log n)$$$ итераций в бинарном поиске по ответу и $$$\text{O}(n)$$$ операций на каждой итерации.

Итоговая сложность — $$$\text{O}(n \log n)$$$

Пусть массив $$$a$$$ длины $$$n$$$ — некоторый набор входных данных к задаче.

Пусть $$$r$$$ и $$$r'$$$ — массивы длины $$$n$$$ такие, что $$$\forall i : 0 \leq r'_i \leq r_i$$$.

Утверждение 1: Пусть $$$\exists$$$ перестановка $$$p$$$ такая, что башня с индексом $$$i$$$ обрушается $$$p_i$$$-ая по порядку, и в результате получается массив $$$r$$$. Тогда $$$\exists$$$ перестановка $$$p'$$$ такая, что башня с индексом $$$i$$$ обрушается $$$p'_i$$$-ая по порядку, и в результате получается массив $$$r'$$$.

$$$\square$$$

Пусть $$$s_i$$$ — суммарное количество башен, которые когда-либо падали на позицию $$$i$$$ при обрушении башен в порядке $$$p$$$. Отметим, что из них $$$r_i$$$ башен были обрушены позже, чем $$$i$$$-я, а остальные — раньше. А высота башни $$$i$$$ в момент обрушения равна $$$a_i + (s_i - r_i)$$$.

Предположение индукции: Существует перестановка $$$p^{(k)}$$$ чисел от $$$1$$$ до $$$k \leq n$$$ такая, что если обрушить $$$i$$$-ю башню $$$p^{(k)}_i$$$-ой по счёту, то:

1. В итоге на $$$i$$$-й позиции будет башня высоты $$$r'_i$$$.

2. Количество (пусть $$$s^{(k)}_i$$$) башен, которые упали на позицию $$$i$$$ при обрушении башен в порядке $$$p^{(k)}$$$, больше либо равно чем $$$s_i$$$.

База индукции: Перестановка $$$p^{(1)} = [1]$$$. После обрушения высота башни становится равной $$$0$$$, поэтому $$$r'_1 = r_1 = 0$$$ в любом итоговом массиве. $$$s^{(1)}_1 = s_1 = 0$$$.

Переход индукции: Пусть перестановка $$$p^{(k - 1)}$$$ существует. Докажем существование $$$p^{(k)}$$$.

$$$\forall i \leq k - 1$$$ высота $$$i$$$-й башни в момент обрушения при порядке $$$p^{(k - 1)}$$$ не меньше, чем при порядке $$$p$$$:

Из этого следует, что при обрушении в порядке $$$p^{(k - 1)}$$$ на позицию $$$k$$$ упадёт не менее чем $$$s_k$$$ башен (пусть их количество равно $$$x \geq s_k \geq r'_k$$$). Ведь высоты в момент обрушения всех башен $$$i \lt k$$$ не изменились либо стали больше.

Пусть $$$x \gt r'_k$$$ и башня $$$j$$$ — это $$$(x - r'_k)$$$-ая по счёту башня из упавших на позицию $$$k$$$. Тогда обрушим башню $$$k$$$ сразу после башни $$$j$$$. Если же $$$x = r'_k$$$, то обрушим башню $$$k$$$ первой. В обоих случаях после обрушения $$$k$$$ на неё упадёт $$$r'_k$$$ башен и её высота станет равна $$$r'_k$$$.

То есть, формально, при $$$x \gt r'_k$$$ переставновка $$$p^{(k)}$$$ строится следующим образом:

1. $$$\forall i \lt k : p^{(k - 1)}_i \leq p^{(k - 1)}_j \Rightarrow p^{(k)}_i = p^{(k - 1)}_i$$$

2. $$$p^{(k)}_k = p^{(k - 1)}_j + 1$$$

3. $$$\forall i \lt k : p^{(k - 1)}_i \gt p^{(k - 1)}_j \Rightarrow p^{(k)}_i = p^{(k - 1)}_i + 1$$$

А при $$$x = r'_k$$$:

1. $$$p^{(k)}_k = 1$$$

2. $$$\forall i \lt k : p^{(k)}_i = p^{(k - 1)}_i + 1$$$

Массив $$$s^{(k)}$$$ строится как $$$\forall i \lt k : s^{(k)}_i = s^{(k - 1)}_i$$$ и $$$s^{(k)}_k = x$$$.

Индукция доказана. Значит положим $$$p' = p^{(n)}$$$, и утверждение доказано.

$$$\blacksquare$$$

Следствие 1: Если мы можем получить $$$\text{MEX}(r) \gt 0$$$ в качестве ответа на задачу при итоговом массиве $$$r$$$, то мы также можем получить $$$\text{MEX}(r) - 1$$$ в качестве ответа на задачу.

$$$\square$$$

Положим $$$r'_i = \max(0, r_i - 1)$$$. Тогда, по утверждению 1, $$$r'$$$ возможно получить как итоговый массив. $$$\text{MEX}(r') = \text{MEX}(r) - 1$$$.

$$$\blacksquare$$$

Следствие 2: Если мы можем получить $$$\text{MEX}(r)$$$ в качестве ответа на задачу при итоговом массиве $$$r$$$, то мы можем получить $$$\text{MEX}(r') = \text{MEX}(r)$$$ при итоговом массиве $$$r'$$$, где $$$r'_i = \max(0, (\text{MEX}(r) - 1) - (n - i))$$$.

$$$\square$$$

По утверждению 1, $$$r'$$$ возможно получить как итоговый массив.

$$$\blacksquare$$$

Можно применить бинарный поиск по ответу (из следствия 1), а на каждой его итерации при проверке ответа $$$x$$$ проверять, можем ли мы получить итоговый массив $$$r$$$ вида $$$r_i = \max(0, (x - 1) - (n - i))$$$ (из следствия 2).

#include <cstdio>
#include <algorithm>
#include <cstring>

#define S 100005

typedef long long l;
 
l a[S], d[S], n;

bool check(l ans) {
    memset(d, 0, sizeof(l) * n);
    l acc = 0;
    
    for (l i = 0; i < n; ++i) {
        acc -= d[i];
        
        l need = std::max(0LL, i - (n - ans));
        if (acc < need) return false;
        
        l end = i + a[i] + (acc++) - need + 1;
        if (end < n) ++d[end];
    }
    
    return true;
}

void solve() {
    scanf("%lld", &n);
    for (l i = 0; i < n; ++i) scanf("%lld", &a[i]);
    
    l le = 1, ri = n + 1, mid;
    while (ri - le > 1) {
        mid = (le + ri) / 2;
        if (check(mid)) le = mid;
        else ri = mid;
    }
    
    printf("%lld\n", le);
}

int main() {
    l tc; scanf("%lld", &tc);
    while (tc--) solve();
}