#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int testcases;
    cin >> testcases;
    for (int t = 1; t <= testcases; t++)
    {
        int n;
        cin >> n;
        vector<int> v(n);
        for (int j = 0; j < n; j++)
        {
            cin >> v[j];
        }
        sort(v.begin(), v.end());
        cout << 2 * (v[n - 1] - v[0]) + 2 * (v[n - 2] - v[1]) << endl;
    }
}

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)
    ans = 2 * (a[n - 1] - a[0] + a[n - 2] - a[1])
    print(ans)

Что мы знаем о расположении мин, если мы сделаем запрос "? 1 1"?

Для получение любого достижимого $$$m$$$ достаточно двух операций.

Давайте определим все достижимые $$$m$$$ для данного $$$n$$$.

Если $$$n$$$ является степенью $$$2$$$-ки, тогда мы не можем его разбить, соответственно, не существует никаких достижимых $$$m < n$$$. Иначе, если $$$n$$$ содержит хотя бы два единичных бита, давайте обозначим старший единичный бит как $$$a$$$, и второй старший единичный бит как $$$b$$$. То есть $$$n = 2^a + 2 ^ b + r$$$, где $$$r < 2 ^ b$$$, $$$a > b$$$.

Факт 1: Все значения $$$m$$$ меньшие $$$n$$$ достижимы, если их старший единичный бит не лежит между $$$b+1$$$ и $$$a-1$$$.

Пример: К примеру, $$$1001????$$$ может быть разбито на $$$1000????$$$ и $$$0001????$$$, или $$$1001????$$$ и $$$0000????$$$. При любом раскладе мы не может изменить $$$6$$$-й и $$$7$$$-й биты.

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

Случай 1: Если старший единичный бит $$$m$$$ на позиции $$$\leq b$$$.

Выполним первую операцию вида $$$2^{b+1} - 1$$$ и $$$n \oplus (2^{b+1} - 1)$$$ ($$$10001????$$$ -> $$$10000????$$$ и $$$000011111$$$ в бинарном виде). Тогда любая подмаска числа $$$2^{b+1} - 1$$$ ($$$000011111$$$ в бинарном виде) может быть достигнута на следующем шаге.

Случай 2: Если старший единичный бит $$$m$$$ на позиции $$$a$$$.

Если старший единичный бит $$$m$$$ на позиции $$$a$$$, тогда $$$m$$$ может быть достигнута за одну операцию $$$m$$$ и $$$m \oplus n$$$, поскольку $$$m < n$$$ по условию, и $$$n \oplus m$$$ имеет свой старший единичный бит на позиции $$$< a$$$, а значит оно строго меньше $$$n$$$.

#include<bits/stdc++.h>

using namespace std;
 
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    ll t;
    cin >> t;
    
    while (t--) {
        ll n, m;
        cin >> n >> m;
        
        ll hi = 0, sec_hi = 0;
        for (ll p = (1LL<<62); p > 0; p >>= 1) {
            if (p & n) {
                if (!hi) hi = p;
                else if (!sec_hi) sec_hi = p;
            }
        }
        bool flag = (sec_hi && ((m & hi) || (m < sec_hi*2)));
        if (!flag) {
            cout << -1 << '\n';
            continue;
        }
        vector<ll> ans = {n, m};
        if (!(m & hi) && !(m & sec_hi)) ans = {n, m^sec_hi, m};
        
        cout << (ll)ans.size()-1 << '\n';
        for (auto &x: ans) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

Если оба числа $$$p_1$$$ и $$$p_2$$$ являются степенями $$$2$$$, то это проигрышное состояние, поскольку вы не можете провести операцию разбиения ни на одном из них.

Если хотя бы одно из чисел $$$p_1$$$ или $$$p_2$$$ имеет два единичных бита, то это выигрышное состояние.

Факт 1: Если $$$p_1$$$ имеет нечетное количество единичных битов, тогда оно обязательно будет разбито на два числа, где одно содержит четное количество битов, а другое нечетное.

Факт 2: Если $$$p_1$$$ или $$$p_2$$$ имеет четное количество единичных битов, то оно может быть разбито на два числа с нечетным количество единичных битов.

Объяснение : Пусть этим числом будет $$$p_1$$$. Тогда разобьем его на $$$2^{msb \text{ of } p_1}$$$ и $$$p_1 \oplus 2^{msb \text{ of } p_1}$$$. Где $$$msb$$$ — старший единичный бит.

Если оппонент выбирает $$$2^{msb \text{ of } p_1}$$$, он моментально проигрывает (причина — Подсказка $$$1$$$), поэтому он форсированно выбирают другое число с нечетным количеством битов. Из Факта $$$1$$$ мы можем заключить, что на следующем ходе мы снова сможем выбрать число с нечетным количеством битов.

Поскольку мы каждый раз избавляемся от самого старшего единичного бита, игра продолжится не дольше чем $$$60$$$ ходов игрока, стоящего в выигрышной позиции.

Следовательно, будучи Алисой, мы хотим ходить первыми, если $$$n$$$ имеет четное количество единичных битов, и ходить вторыми, если количество единичных битов нечетно. Будем играть используя стратегию, которая описана выше.

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int testcases;cin>>testcases;
 
    for(int testcase=1;testcase<=testcases;testcase++){
        long long n;cin>>n;
        long long curr=n;
        int parity=0;
        if(__builtin_popcountll(n)%2){
            cout<<"secoNd"<<endl;
        }else{
            cout<<"firSt"<<endl;
            parity=1;
        }
        int turn=0;
        while(1){
            if(turn%2==parity){
                long long p1,p2;cin>>p1>>p2;
                if (p1 == 0 && p2 == 0)
                    break;
                if(__builtin_popcountll(p1)%2==0){
                    curr=p1;
                }else{
                    curr=p2;
                }
            }else{
                int pos=0;
                for(int i=0;(1ll<<i)<curr;i++){
                    if(curr&(1ll<<i)){
                        pos=i;
                    }
                }
                long long p1=(1ll<<pos);
                long long p2=curr^p1;
                cout<<p1<<" "<<p2<<endl;
                curr = p1;
            }
            turn++;
        }
    }
}

Факт 1: Если для некоторой тройки $$$(x, y, z)$$$ их попарные НОДы равняются их общему НОДу (это значит, что $$$(x, y, z)$$$ = $$$(g * X, g * Y, g * Z)$$$ где $$$(X, Y, Z)$$$ попарно взаимнопросты), тогда применение операции к ним дает $$$(g * X * Y, g * X * Z,g * Y * Z)$$$, и посмотрев на подпоследовательности размера РОВНО 2, мы найдем все три НОДа: $$$x$$$, $$$y$$$, $$$z$$$. Назовем такую тройку КРАСИВОЙ.

Результат: Если мы можем разбить все значение на независимые КРАСИВЫЕ тройки, тогда просто можно применить операцию к каждой из них, и задача решена.

Факт 2: Мы можем совсем не трогать значения $$$\leq \frac{n}{2}$$$. Рассмотрим $$$x \leq \frac{n}{2}$$$, тогда имеется и $$$2 * x \leq n$$$. Если мы не трогаем $$$x$$$ совсем, то мы всегда будем иметь некоторое другое значение, которое делится на $$$x$$$ (легко заметить, что применение операции на таком значении всегда производит хотя бы одно другое значение, которое тоже делится на $$$x$$$), таким образом мы всегда будем иметь НОД равный $$$x$$$, взяв подпоследовательность $$$(x, x * A)$$$.

Факт 3: Последовательные целые числа $$$(x, x+1, x+2, ..., x+11)$$$ можно разбить на $$$4$$$ независимые КРАСИВЫЕ тройки размера $$$3$$$, при условии $$$(x+11) \% 4$$$ равняется $$$2$$$ или $$$1$$$.

Для $$$(x+11) \% 4 = 2$$$: Тройки $$$(x, x+1, x+2)$$$, $$$(x+4, x+5, x+6)$$$ и $$$(x+8, x+9, x+10)$$$ являются КРАСИВЫМИ, первое и третье числа в каждой тройке являются нечетными, второе четным, поэтому их общий и попарные НОДы равны $$$1$$$. Тройка $$$(x+3, x+7, x+11)$$$ является КРАСИВОЙ, ибо она представимы в виде $$$(2*(2*n-1)$$$, $$$2*(2*n)$$$, $$$2*(2*n+1))$$$, соответственно их общий и попарные НОДЫ равны $$$2$$$.

Для $$$(x+11) \% 4 = 1$$$: Тройки $$$(x, x+4, x+8)$$$, $$$(x+1, x+2, x+3)$$$, $$$(x+5, x+6, x+7)$$$ и $$$(x+9, x+10, x+11)$$$ являются КРАСИВЫМИ. Применима та же логика что и для $$$(x+11) \% 4 = 2$$$,

Если $$$n \% 4 = 3$$$, то мы можем выполнить операцию $$$(1, 2, n)$$$, и если $$$n \% 4 = 0$$$ можем выполнить операцию $$$(1, n-1, n)$$$.

Давайте сгруппируем оставшиеся элементы, начиная с конца в группы размера $$$12$$$ пока мы не перескочим ниже $$$\frac{n}{2}$$$.

Итого можно посчитать, что мы использовали не более $$$\lfloor \frac{n}{6} \rfloor + 5$$$ операций.

Решения для $$$n \leq 13$$$ должны быть найдены вручную.

#include<bits/stdc++.h>
 
using namespace std;
vector<vector<vector<int>>> pans(14);
int main(){
 
    ios::sync_with_stdio(false), cin.tie(nullptr);
 
    int t;cin>>t;
 
    pans[3]={{1,2,3}};
    pans[4]={{1,3,4}};
    pans[5]={{3,4,5}};
    pans[6]={{1,3,5},{2,4,6}};
    pans[7]={{2,4,6},{3,5,7}};
    pans[8]={{2,6,8},{3,5,7}};
    pans[9]={{1,3,5},{2,4,6},{7,8,9}};
    pans[10]={{3,4,5},{2,6,8},{7,9,10}};
    pans[11]={{2,6,8},{3,5,7},{9,10,11}};
    pans[12]={{1,11,12},{6,8,10},{5,7,9}};
    pans[13]={{1,12,13},{7,9,11},{6,8,10}};
    for(int tt=0;tt<t;tt++){
        int n;cin>>n;
        if(n<=2){
            cout<<-1<<endl;
        }else if(n<14){
            cout<<pans[n].size()<<endl;
            for(auto w: pans[n]){
                cout<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl;
            }
        }else{
            vector<int> v(n);
            for(int i=0;i<n;i++){
                v[i]=i+1;
            }
            vector<vector<int>> ans;
            while (2*v.size()>n){
                if(v.size()%4==2){
                    vector<int> buf;
                    for(int i=0;i<12;i++){
                        buf.push_back(v.back());
                        v.pop_back();
                    }
                    reverse(buf.begin(),buf.end());
                    ans.push_back({buf[0],buf[1],buf[2]});
                    ans.push_back({buf[4],buf[5],buf[6]});
                    ans.push_back({buf[8],buf[9],buf[10]});
                    ans.push_back({buf[3],buf[7],buf[11]});
                }else if(v.size()%4==1){
                    vector<int> buf;
                    for(int i=0;i<12;i++){
                        buf.push_back(v.back());
                        v.pop_back();
                    }
                    reverse(buf.begin(),buf.end());
                    ans.push_back({buf[1],buf[2],buf[3]});
                    ans.push_back({buf[5],buf[6],buf[7]});
                    ans.push_back({buf[9],buf[10],buf[11]});
                    ans.push_back({buf[0],buf[4],buf[8]});
                }else if(v.size()%4==3){
                    vector<int> buf;
                    buf.push_back(v.back());
                    v.pop_back();
                    buf.push_back(2);
                    buf.push_back(1);
                    reverse(buf.begin(),buf.end());
                    ans.push_back({buf[0],buf[1],buf[2]});
                }else{
                    vector<int> buf;
                    buf.push_back(v.back());
                    v.pop_back();
                    buf.push_back(v.back());
                    v.pop_back();
                    buf.push_back(1);
                    reverse(buf.begin(),buf.end());
                    ans.push_back({buf[0],buf[1],buf[2]});
                }
            }
            cout<<ans.size()<<endl;
            for(auto w: ans){
                cout<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl;
            }
        }
    }
}