Пусть $$$t$$$ — перевернутая строка $$$s$$$. Заметим, что нам выгодно использовать операцию 1 (добавление перевернутой строки в конец) не более одного раза. Действительно, получив какую-то строку, оставшиеся операции потратим просто на переворот строки. Тем самым получим исходную строку, либо перевернутую в зависимости от четности количества оставшихся операций.

Несложно увидеть, что ответ всегда будет иметь префикс либо $$$s$$$, либо $$$t$$$. Тогда найдем две лексикографически минимальные строки с префиксом $$$s$$$ и $$$t$$$. Это будут строки:

• $$$s$$$, перевернем $$$n$$$ раз строку (так как $$$n$$$ четное, каждые 2 операции мы возвращаем строку в изначальную)
• $$$t + s$$$, изначально перевернем строку, добавим перевернутую строку в конец, после чего перевернем строку $$$n - 2$$$ раза.

Ответом будет лексикографически минимальная строка из $$$s$$$ и $$$t + s$$$

#include <bits/stdc++.h>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tt;
    std::cin >> tt;
    while (tt--) {
        int n;
        std::cin >> n;
        std::string s;
        std::cin >> s;
        std::string t = s;
        reverse(t.begin(), t.end());
        std::cout << std::min(s, t + s) << "\n";
    }

    return 0;
}

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    t = s[::-1]
    print(min(s, t + s))

Допустим, мы разбили массив корректно на $$$k > 2$$$ подотрезков — $$$(1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$$$. Тогда заметим, что мы можем объединить первые два подотрезка и разбиение все еще будет корректно, так как числа с 0 до $$$mex - 1$$$ встречаются на этих двух подотрезках и число $$$mex$$$ на них не встречается. Следовательно если существует разбиение на $$$k > 2$$$ подотрезков, то существует и для $$$k - 1$$$ подотрезков.

Следовательно достаточно проверить существует ли разбиение массива на $$$k = 2$$$ отрезка, сделать это можно за $$$O(n)$$$ посчитав $$$\operatorname{MEX}$$$ на каждом префиксе и суффиксе, после чего проверить существует ли такое $$$i$$$, что $$$\operatorname{MEX}(1, i) = \operatorname{MEX}(i + 1, n)$$$.

/* Includes */
#include <bits/stdc++.h>
 
/* Using libraries */
using namespace std;

/* Defines */
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define vc vector
#define pii pair <int, int>
#define int long long
 
void solve () {
    int n;
    cin >> n;
    vc <int> a(n);
    vc <int> cnt1(n + 1), cnt2(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        cnt2[a[i]]++;
    }
    int mex1 = 0, mex2 = 0;
    while (cnt2[mex2])
        ++mex2;
    for (int i = 0; i < n; ++i) {
        cnt1[a[i]]++;
        if (--cnt2[a[i]] == 0 && mex2 > a[i]) {
            mex2 = a[i];
        }
        while (mex2 && !cnt2[mex2 - 1])
            --mex2;
        while (cnt1[mex1])
            ++mex1;
        if (mex1 == mex2) {
            cout << "2\n";
            cout << 1 << " " << i + 1 << "\n";
            cout << i + 2 << " " << n << "\n";
            return;
        }
    }
    cout << "-1\n";
}

signed main() {
    fast;
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    cur_mex = 0
    cur_have = [0] * (n + 1)
    for el in a:
        cur_have[el] += 1
    while cur_have[cur_mex]:
        cur_mex += 1

    another_mex = 0
    another_have = [0] * (n + 1)
    for i in range(n):
        cur_have[a[i]] -= 1
        if cur_have[a[i]] == 0 and cur_mex > a[i]:
            cur_mex = a[i]

        another_have[a[i]] += 1
        while another_have[another_mex]:
            another_mex += 1

        if cur_mex == another_mex:
            print(2)
            print("1 " + str(i + 1))
            print(str(i + 2) + " " + str(n))
            return

    print(-1)


t = int(input())
for _ in range(t):
    solve()

Пусть порядок в ответе $$$p_1, p_2, \ldots, p_k$$$. Заметим, что в оптимальном ответе будет выполняться $$$b_{p_1} \leq b_{p_2} \leq \ldots \leq b_{p_k}$$$. Несложно доказать, что такой порядок минимизирует сумму модулей разности соседних элементов в массиве $$$b$$$. Тогда, данная сумма превратится в $$$b_{p_k} - b_{p_1}$$$, то есть разность наибольшего значения $$$b$$$ и наименьшего в наборе сообщений.

Давайте отсортируем пары $$$(a_i, b_i)$$$ в порядке увелечения $$$b_i$$$. Зафиксируем минимальное значение в наборе сообщений $$$b_l$$$ и максимальное значение $$$b_r$$$. Заметим, что сумма модулей разности $$$b$$$ в ответе не изменится если брать значения $$$b_l \leq b_i \leq b_r$$$. Тогда, задача сводится к поиску максимального количества сообщений, чтобы $$$\sum a \leq L - (b_r - b_l)$$$.

Переберем $$$b_l$$$ и $$$b_r$$$. Применим жадный алгоритм, отсортируем все значения $$$a_i$$$ ($$$l \leq i \leq r$$$), и будем набирать значения пока время не превысит $$$L$$$. Данное решение работает за $$$O(n^3\log{}n)$$$, что слишком медленно.

Ускорим решение. Во время того как будем перебирать $$$b_r$$$, будем поддерживать структуру данных, которая позволяет добавлять элемент, удалять максимум, получать максимум (в C++ существуют $$$\textit{multiset}$$$ и $$$\textit{priority_queue}$$$). В данной структуре данных будем поддерживать минимальные значения $$$a$$$, чтобы сумма времени не превышала $$$L$$$. Тогда, если текущее время превышает $$$L$$$, будем удалять из структуры, пока текущее время станет не более $$$L$$$. Таких удалений будет не более чем $$$n$$$. Получили решение за $$$O(n^2\log{}n)$$$, что спокойно заходит.

#include <bits/stdc++.h>

signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while (t--) {
        int n, L;
        std::cin >> n >> L;
        std::vector<std::pair<int, int>> v(n);
        for (int i = 0 ; i < n ; i++) {
            std::cin >> v[i].second >> v[i].first;
        }
        std::sort(v.begin(), v.end());

        int ans = 0;
        for (int l = 0 ; l < n ; l++) {
            std::multiset<int> s;
            int cur = 0;
            for (int r = l ; r < n ; r++) {
                s.insert(v[r].second);
                cur += v[r].second;
                while (!s.empty() && v[r].first - v[l].first + cur > L) {
                    int max_value = *s.rbegin();
                    cur -= max_value;
                    s.extract(max_value);
                }
                ans = std::max(ans, (int) s.size());
            }
        }

        std::cout << ans << "\n";
    }

    return 0;
}

import heapq
import sys

input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, L = map(int, input().split())
    v = []
    for i in range(n):
        a, b = map(int, input().split())
        v.append((b, a))
    v.sort()

    ans = 0
    for l in range(n):
        pq = []
        heapq.heapify(pq)
        cur = 0
        size = 0
        for r in range(l, n):
            heapq.heappush(pq, -v[r][1])
            size += 1
            cur += v[r][1]
            while size and v[r][0] - v[l][0] + cur > L:
                maxx = -heapq.heappop(pq)
                cur -= maxx
                size -= 1
            ans = max(ans, size)

    print(ans)

Применим формулу включений-исключений. Тогда ответом на задачу будет: $$$\mathrm{cnt}(x, y) - \mathrm{cnt}(x, y: x + y \in s) - \mathrm{cnt}(x, y: y - x \in s) + \mathrm{cnt}(x, y: x + y, y - x \in s)$$$, $$$\mathrm{cnt}(x, y)$$$ означает количество возможных пар $$$x, y$$$. Посчитаем каждое значение по отдельности.

Количество возможных пар $$$x, y$$$ — $$$\frac{(c+1)\cdot(c+2)}{2}$$$.

Количество пар $$$x, y: x + y \in s$$$. Переберем значение суммы $$$s_i$$$, пусть $$$x + y = s_i$$$, тогда для $$$0 \leq x \leq \lfloor \frac{s_i}{2} \rfloor$$$ будет соотвествовать ровно один $$$y$$$, то есть количество пар с такой суммой $$$\lfloor \frac{s_i}{2} \rfloor + 1$$$.

Количество пар $$$x, y: y - x \in s$$$. Переберем значение разности $$$s_i$$$, пусть $$$y - x = s_i$$$, тогда для $$$s_i \leq y \leq c$$$ будет соотвествовать ровно один $$$x$$$, то есть количество пар с такой разностью $$$c - s_i + 1$$$.

Количество пар $$$x, y: x + y, y - x \in s$$$. Пусть $$$x+y=s_i$$$, $$$y-x=s_j$$$, тогда $$$x = \frac{s_i - s_j}{2}$$$, а $$$y = \frac{s_i+s_j}{2}$$$. Если $$$s_i, s_j$$$ разной четности, то такие $$$x, y$$$ не подойдут, поскольку они будут нецелыми, иначе такие $$$x, y$$$ подойдут и нужно добавить эту пару. Тогда посчитаем количество четных и нечетных чисел в $$$s$$$ — $$$even$$$ и $$$odd$$$ соотвественно. Тогда количество таких пар $$$\frac{even\cdot(even+1)}{2}+\frac{odd\cdot(odd+1)}{2}$$$.

С помощью всех этих количеств можно посчитать ответ. Итоговая асимптотика $$$O(n)$$$. Также задачу можно решить за $$$O(n \cdot \log n)$$$ или $$$O(n)$$$ другими способами.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve_case() {
    int n, c;
    cin >> n >> c;
    vector<int> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];
    int odd = 0, even = 0;
    ll ans = 1ll * (c + 1) * (c + 2) / 2;
    for (int i = 0; i < n; i++) {
        ans -= s[i] / 2 + 1;
        ans -= c - s[i] + 1;
        if (s[i] % 2 == 0) {
            even++;
        } else {
            odd++;
        }
    }
    ans += 1ll * even * (even + 1) / 2;
    ans += 1ll * odd * (odd + 1) / 2;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve_case();
    }
}

def solve_case() :
    n, c = map(int, input().split())
    s = list(map(int, input().split()))
    ans = (c + 1) * (c + 2) // 2
    even, odd = 0, 0
    for i in range(n):
        ans -= s[i] // 2 + 1
        ans -= c - s[i] + 1
        if s[i] % 2 == 0:
            even += 1
        else:
            odd += 1
    ans += even * (even + 1) // 2
    ans += odd * (odd + 1) // 2
    print(ans)

t = int(input())
for test in range(t):
    solve_case()

Решим задачу, когда $$$x = 0$$$. Тогда будем перебирать бит от старших к младшим и пытаться добавить их в ответ. Допустим мы перебираем бит $$$i$$$, тогда если такой бит встречается $$$c$$$ раз среди чисел $$$y$$$ существует несколько случаев:

• $$$c = 0$$$ — данный бит нельзя добавить в ответ
• $$$c = 1$$$ — данный бит входит в ответ, добавим его
• $$$c > 1$$$ — особый случай, ведь мы можем для одного числа где присутствует бит $$$i$$$ поставить его, а для другого числа можно поставить все биты $$$j < i$$$.

Следовательно, если мы встретили какой-то бит $$$i$$$ который встречается больше одного раза, то все биты $$$j \le i$$$ тоже входят в ответ. Теперь решим исходную задачу, для этого возьмем пару $$$(x_i, y_i)$$$ и найдем побитовый наибольший общий префикс — пусть это будет число $$$w$$$. Тогда понятно, что все биты из $$$w$$$ будут входить в ответ, тогда сделаем новую пару $$$(x'_i, y'_i)$$$ = $$$(x_i - w, y_i - w)$$$, и запомним число $$$w_i$$$. Теперь заметим, что число $$$y'_i - 1 \ge x'_i$$$. Зачем нужен этот факт? Вспомним, что при случае когда какой-то бит встречался более одного раза, то мы добавляли в ответ и все меньше биты. Для этого мы ставили в данной позиции число равное $$$2^i - 1$$$ (ну и другие биты большие $$$i$$$), но если $$$y'_i - 1 \ge x'_i$$$, то мы всегда сможем добавлять все такие биты.

Следовательно алгоритм решения для запроса $$$j$$$ следующий:

• Возьмем Побитовое ИЛИ всех $$$w_i$$$ для $$$l_j \le i \le r_j$$$, пусть это будет число $$$W$$$
• Переберем бит $$$i$$$ и подобно случаю $$$x = 0$$$ рассмотрим те же случаи, но для массива $$$y'$$$. Также нужно учитывать, что бит встречается в $$$W$$$.

Реализовать данное решение можно за $$$O(n \cdot \log n)$$$ с помощью префиксных сумм по каждому биту. Также существует решение, использующее дерево отрезков, поэтому задача решается и с запросами изменения.

/* Includes */
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
 
/* Using libraries */
using namespace std;
 
/* Defines */
template <class T>
using vc = vector <T>;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
 
template<class T>
void output(T &a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
 
template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
const int N = 2e5;
const int bit = 30;
 
struct segtree {
    vc <int> t; int n;
    segtree (int n) : n(n) {
        t.resize(n * 2);
    }
    void upd (int i, int x) {
        for (t[i += n] = x; i > 1; i >>= 1) {
            t[i >> 1] = t[i] | t[i ^ 1];
        }
    }
    int get (int l, int r) {
        int res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                res |= t[l++];
            if (r & 1)
                res |= t[--r];
        }
        return res;
    }
};
 
int n;
int l[N], r[N];
int w[N];
void fix () {
    for (int i = 0; i < n; ++i) {
        if (l[i] == r[i]) {
            w[i] = l[i];
            l[i] = r[i] = 0;
            continue;
        }
        int pref = (1 << (__lg(l[i] ^ r[i]) + 1)) - 1;
        w[i] = r[i] - (r[i] & pref);
        r[i] &= pref;
        l[i] &= pref;
    }
}
 
void solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
    }
    fix();
    segtree t(n);
    vc <vc <int>> bits(bit, vc <int> (n + 1));
    for (int i = 0; i < n; ++i) {
        t.upd(i, w[i]);
        for (int j = 0; j < bit; ++j) {
            bits[j][i + 1] = bits[j][i];
            if (r[i] >> j & 1) {
                bits[j][i + 1]++;
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y; --x;
        int ans = t.get(x, y);
        for (int j = bit - 1; j >= 0; --j) {
            int cnt = bits[j][y] - bits[j][x] + (ans >> j & 1);
            if (cnt > 1) {
                ans |= (2 << j) - 1;
                break;
            } else if (cnt == 1) {
                ans |= 1 << j;
            }
        }
        cout << ans << ' ';
    }
    cout << "\n";
}
 
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

Зафиксируем какую-то вершину $$$v$$$, для которой считается ответ. Пусть степень вершины $$$v$$$ в дереве $$$deg_v$$$, тогда понятно, что нужно добавить $$$deg_v - 1$$$ ребер. Рассмотрим компоненты, которые появляются после удаления $$$v$$$. Тогда хочется используя новые ребра объединить все компоненты одну, используя минимальную суммарную стоимость. Это тоже самое, что и найти минимальное остовное дерево в графе, где вершины это компоненты, который получились после удаления $$$v$$$, и для каждых $$$a, b$$$ проведено ребро весом $$$|a - b|$$$ между компонентами, содержащих $$$a$$$ и $$$b$$$.

Давайте симмулировать алгоритм Крускала для этого графа. Рассмотрим все единичные ребра в этом графе: $$$(1, 2), (2, 3), ..., (v - 2, v - 1), (v + 1, v + 2), ..., (n - 1, n)$$$. Понятно, что используя единичные ребра вершины с номерами $$$[1, v - 1]$$$ точно окажутся в одной компоненте, и вершины с номерами $$$[v + 1, n]$$$ тоже окажутся в одной компоненты. Чтобы объединить эти две компоненты, оптимально будет добавить ребро $$$(v - 1, v + 1)$$$.

Получается, что достаточно рассматривать только все единичные ребра и ребро $$$(v - 1, v + 1)$$$. Давайте ограничим количество единичных ребер до $$$O(deg_v)$$$. Для этого посчитаем в каждой компоненте $$$u$$$ $$$mn_u$$$ и $$$mx_u$$$ — минимум и максимум в компоненте соотвественно. Утверждение: среди единичных ребер достаточно рассматривать ребра вида $$$(mn_u, mn_u - 1)$$$, $$$(mx_u, mx_u + 1)$$$.

Найти для каждой компоненты $$$mn_u$$$, $$$mx_u$$$ нетяжело, осталось для вершины $$$v$$$ находить какие компоненты соединяют ребра $$$(mn_u, mn_u - 1)$$$, $$$(mx_u, mx_u + 1)$$$. Это можно делать бинпоиском по эйлеровому обходу дерева. После чего можно запустить алгоритм Крускала и посчитать ответ.

Оценим время работы. Для конкретной вершины $$$v$$$ время работы будет $$$deg_v \cdot \log n$$$, а значит суммарное время работы $$$O(n \cdot \log n)$$$.

В зависимости от реализации последнего шага можно решать задачу за $$$O(n)$$$, $$$O(n \cdot \alpha(n))$$$, где $$$\alpha (n)$$$ — обратная функция Аккермана к числу $$$n$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
 
struct DSU {
    vector<int> p, r;
    int comp;
    DSU(int n) : p(n), r(n) {
        iota(p.begin(), p.end(), 0);
        comp = n;
    }
    int find(int v) {
        return (p[v] == v) ? v : p[v] = find(p[v]);
    }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        comp--;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        return true;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i++) {
            int x, y;
            cin >> x >> y;
            x--, y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        vector<int> tin(n), tout(n), l0(n), r0(n);
        vector<int> lup(n), rup(n);
        int timer = 0;
        vector<int> ord;
        function<void(int, int)> dfs = [&](int v, int p) {
            l0[v] = r0[v] = v;
            tin[v] = timer++;
            ord.push_back(v);
            for (int u : g[v]) {
                if (u == p) continue;
                dfs(u, v);
                l0[v] = min(l0[v], l0[u]);
                r0[v] = max(r0[v], r0[u]);
            }
            tout[v] = timer - 1;
        };
        dfs(0, 0);
        function<bool(int, int)> ancestor = [&](int v, int u) {
            return tin[v] <= tin[u] && tin[u] <= tout[v];
        };
        vector<int> pref_min_ord(n + 1, n), suf_min_ord(n + 1, n);
        vector<int> pref_max_ord(n + 1, -1), suf_max_ord(n + 1, -1);
        for (int i = 0; i < n; i++) {
            pref_min_ord[i + 1] = min(pref_min_ord[i], ord[i]);
            pref_max_ord[i + 1] = max(pref_max_ord[i], ord[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            suf_min_ord[i] = min(suf_min_ord[i + 1], ord[i]);
            suf_max_ord[i] = max(suf_max_ord[i + 1], ord[i]);
        }
        for (int id = (int)ord.size() - 1; id >= 0; id--) {
            int v = ord[id];
            lup[v] = min(pref_min_ord[tin[v]], suf_min_ord[tout[v] + 1]);
            rup[v] = max(pref_max_ord[tin[v]], suf_max_ord[tout[v] + 1]);
        }
        vector<vector<pair<int, int>>> ans(n);
        vector<int> weight(n);
        function<void(int, int)> dfs2 = [&](int v, int p) {
            vector<int> all_id, all_tin;
            int idpar = -1;
            for (int id = 0; id < g[v].size(); id++) {
                int u = g[v][id];
                if (u != p) {
                    dfs2(u, v);
                    all_id.push_back(id);
                    all_tin.push_back(tin[u]);
                } else {
                    idpar = id;
                }
            }
            function<int(int)> get_subtree = [&](int u) {
                if (!ancestor(v, u)) return idpar;
                return all_id[upper_bound(all_tin.begin(), all_tin.end(), tin[u]) - all_tin.begin() - 1];
            };
            DSU dsu(g[v].size());
            function<void(int, int)> try_add = [&](int x, int y) {
                if (x == -1 || y == n || x == v || y == v) return;
                if (dsu.join(get_subtree(x), get_subtree(y))) {
                    ans[v].push_back({x, y});
                    weight[v] += abs(x - y);
                }
            };
            for (int u : g[v]) {
                if (u != p) {
                    try_add(l0[u] - 1, l0[u]);
                    try_add(r0[u], r0[u] + 1);
                } else {
                    try_add(lup[v] - 1, lup[v]);
                    try_add(rup[v], rup[v] + 1);
                }
            }
            if (dsu.comp != 1) {
                try_add(v - 1, v + 1);
            }
            assert(dsu.comp == 1);
        };
        dfs2(0, 0);
        for (int i = 0; i < n; i++) {
            cout << weight[i] << " " << ans[i].size() << "\n";
            for (auto [a, b] : ans[i]) {
                cout << a + 1 << " " << b + 1 << "\n";
            }
            cout << "\n";
        }
    }
}