Ответ никогда не превосходит $$$2$$$.

Если строка состоит только из $$$1$$$, то ответ $$$0$$$.

Если все нули идут подряд, то ответ $$$1$$$.

Ответ всегда не превосходит $$$2$$$, потому что $$$\operatorname{MEX}$$$ всей строки не больше $$$2$$$.

Ответ $$$0$$$ только в том случае, если нулей в строке нет совсем.

Теперь необходимо понять, когда ответ $$$1$$$, а когда — $$$2$$$. Сумма $$$\operatorname{MEX}$$$ равна $$$1$$$ только в том случае, если все нули образуют один отрезок без единиц. Тогда мы его вырежем, его $$$\operatorname{MEX}$$$ равен $$$1$$$, всё остальное — единицы, их $$$\operatorname{MEX}$$$ равен $$$0$$$.

Если же нули не образуют один отрезок без единиц, то найдутся два нуля, между которыми единица. Либо эти два нуля в одном отрезке, но тогда и единица с ними, то есть $$$\operatorname{MEX}$$$ равен $$$2$$$. Либо эти два нуля в двух разных отрезках, но тогда сумма $$$\operatorname{MEX}$$$ точно не меньше $$$2$$$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T --> 0) {
        string s;
        cin >> s;
        int zeroes = count(s.begin(), s.end(), '0');
        if (zeroes == 0) {
            cout << 0 << '\n';
            continue;
        }
        int first = s.find('0');
        int last = s.rfind('0');
        if (last - first + 1 == zeroes) {
            cout << 1 << '\n';
        } else {
            cout << 2 << '\n';
        }
    }
    return 0;
}

t = int(input())
for test in range(t):
    s = input()
    zeroes = s.count('0')
    if zeroes == 0:
        print(0)
        continue

    first = s.find('0')
    last = s.rfind('0')
    if last - first + 1 == zeroes:
        print(1)
    else:
        print(2)

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

Будем считать, что $$$dp_i$$$ — ответ на префиксе до $$$i$$$. Тогда есть разные подходы:

Можно пересчитывать динамику, перебирая все возможные значения $$$\operatorname{MEX}$$$ на последнем отрезке. Например, если мы хотим получить $$$\operatorname{MEX}$$$ равный $$$2$$$ на последнем отрезке, то нам нужно найти ближайший $$$0$$$ и ближайшую $$$1$$$ к позиции $$$i$$$. Пусть это $$$last_0$$$ и $$$last_1$$$. Тогда нужно пересчитать динамику как $$$dp_i = \max(dp_i, dp_{j - 1} + 2)$$$, где $$$j = \min(last_0, last_1)$$$, потому что мы берём кратчайший отрезок с концом в $$$i$$$, на котором есть и $$$0$$$, и $$$1$$$, после чего добавляем ответ для этого отрезка и для предыдущего, который кончается в $$$j-1$$$.

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
typedef vector<int> vi;

//Did you REAALLY consider sample tests?
void solve(int tc) {
    string s[2];
    int n;
    cin >> n;
    cin >> s[0] >> s[1];
    vi dp(n + 1, 0);
    vi last(2, -1);
    
    auto take = [&](int i, bool take0, bool take1) {
        int MEX = 0;
        if (take0) {
            if (take1) MEX = 2;
            else MEX = 1;
        }
        
        int index = i;
        if (take0) index = min(index, last[0]);
        if (take1) index = min(index, last[1]);
        
        if (index != -1) return MEX + dp[index - 1];
        return -100000;
    };
    
    FOR(i, 1, n) {
        vi val(2);
        rep(j, 0, 2) last[s[j][i-1] - '0'] = i;
        dp[i] = dp[i-1];
        dp[i] = max(dp[i], take(i, 1, 0));
        dp[i] = max(dp[i], take(i, 0, 1));
        dp[i] = max(dp[i], take(i, 1, 1));
    }
    
    cout << dp[n] << "\n";
}
 
int main() {
    int tests;
    cin >> tests;
    FOR(test, 1, tests) {
        solve(test);
    }
}

Другое возможное решение с динамикой основано на том, что нам никогда не выгодно брать отрезок длины больше $$$x$$$, где $$$x$$$ — какое-то маленькое число. Можно даже ничего не доказывать и выбрать $$$x$$$ с запасом. Существует решение, которое не рассматривает отрезки длины больше, чем $$$5$$$.

#include<bits/stdc++.h>
 
using namespace std;
 
int mex(string s){
  int fl=0;
  for(auto &nx : s){
    if(nx=='0'){fl|=1;}
    else if(nx=='1'){fl|=2;}
  }
  if(fl==3){return 2;}
  if(fl==1){return 1;}
  return 0;
}
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n;
    string s1,s2;
    cin >> n >> s1 >> s2;
    vector<int> dp(n+1,0);
    for(int i=0;i<n;i++){
      string s;
      for(int j=0;j<5;j++){
        if(i+j>=n){break;}
        s.push_back(s1[i+j]);
        s.push_back(s2[i+j]);
        dp[i+j+1]=max(dp[i+j+1],dp[i]+mex(s));
      }
    }
    cout << dp[n] << '\n';
  }
  return 0;
}

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

Научимся решать для случая, когда $$$n=1$$$. Заметим, что нам выгодно каждый раз сажать человека на максимальную из доступных для него позиций.

Как могут располагаться места, доступные для данного человека?

Места, доступные для данного человека могут являться либо подотрезком одного ряда, либо объединением нескольких рядов, суффикса какого-то ряда и префикса какого-то ряда.

Рассмотрим все места в порядке увеличения их номера. Если для каждого места записать уровень зрения человека на этом месте, то полученная последовательность будет неубывающей. Тогда становится понятно, что люди с одинаковым уровнем зрения занимают последовательные места, и для каждого уровня зрения $$$x$$$ мы можем определить, какие последовательные места займут люди с уровнем зрения $$$x$$$.

Теперь поймём, как люди со зрением $$$x$$$ сидят в кинотеатре. Для этого уровня зрения $$$x$$$ мы поняли, что люди с таким зрением должны занять места с номерами от $$$l$$$ до $$$r$$$.

Будем рассаживать людей с одним уровнем зрения жадно. Если все места с $$$l$$$ по $$$r$$$ находятся в одном ряду, то людей необходимо рассаживать в порядке уменьшения номера места. В противном случае, эти места покрывают суффикс одного ряда (возможно, пустой), несколько (возможно, ноль) целых рядов и префикс одного ряда (возможно, пустой). Сначала необходимо рассаживать людей на суффикс в порядке убывания мест. Это точно не хуже других рассадок, потому что места до этого суффикса могут потом занять, что увеличит суммарное неудобство. Места на префиксе нужно занимать в последнюю очередь в порядке убывания мест. Это точно не хуже других рассадок, потому что если посадить людей на префикс раньше, то они могут помешать тем, кто будет садиться правее. Целые ряды надо занимать в порядке убывания мест, что не меняет суммарное неудобство. Таким образом, сначала надо занять суффикс, потом целые ряды, потом префикс, каждый случай в порядке убывания мест.

Благодаря маленькому ограничению на $$$m$$$, мы можем каждый раз пробегать по ряду и смотреть, сколько человек увеличат наше неудобство. Тогда итоговая асимптотика составляет $$$O(nm^2)$$$.

#include <bits/stdc++.h>
#define long long long int
using namespace std;
 
// @author: pashka
 
void solve_test() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(n * m);
    for (int i = 0; i < n * m; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n * m; i++) {
        a[i].second = -a[i].second;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        sort(a.begin() + (m * i), a.begin() + (m * i + m));
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < j; k++) {
                if (a[i * m + k].second > a[i * m + j].second) res++;
            }
        }
    }
    cout <<res << "\n";
}
 
int main() {
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        solve_test();
    }
 
    return 0;
}

Пересадка почки на лист уменьшает общее количество листьев на $$$1$$$.

Можно пересаживать почки так, чтобы в итоге остался только корень, почки, подвешенные к корню, и листья, подвешенные к почкам и корню.

Теперь ответ выражается через общее количество вершин и количество почек в зависимости от того, есть ли лист, подвешенный к корню.

Переподвешивая почку от родителя к корню, количество листьев либо не изменяется (если у родителя были другие дети), либо увеличивается на $$$1$$$. При этом хуже не станет, потому что если есть листья, кроме листьев этой почки, то почку можно подвесить к этому листу, гарантированно уменьшив количство листьев на $$$1$$$. Тогда давайте будем пересаживать почки к корню до тех пор, пока не кончатся почки, подвешенные не к корню.

Теперь пусть все почки подвешены к корню, и их количество равно $$$k$$$. Тогда ответ $$$n - 2 \cdot k$$$, если нет листа, подвешенного к корню, либо $$$n - 2 \cdot k - 1$$$, если есть лист подвешенный к корню. Почему это так? Всего листьев изначально $$$n - k - 1$$$ (общее количество вершин — количество почек — корень). Если к корню подвешен лист, то к этому листу можно подвесить почку, к её листу подвесить ещё одну почку, и так далее, пока не кончатся все $$$k$$$ почек. В итоге получили $$$k$$$ переподвешиваний, каждое из которых уменьшает количество листьев на $$$1$$$, тогда ответ $$$n - k - 1 - k = n - 2 \cdot k - 1$$$. Если же листа, подвешенного к корню нет, то будем подвешивать сразу к листу какой-то почки, получим уже $$$k - 1$$$ переподвешивание, что в итоге даёт ответ $$$n - k - 1 - (k - 1) = n - 2 \cdot k$$$. Сделать меньше невозможно, потому что каждое переподвешивание почки от корня уменьшает количество листьев на $$$\le 1$$$, а в нашем алгоритме каждое переподвешивание уменьшает количество листьев ровно на $$$1$$$, и мы задействуем все переподвешивания.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
vector<int> type; // -1  -- default, 0 -- root, 1 -- leaf, 2 -- bud

void dfs(int v, int p) {
    bool leaves = false;
    for (auto to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        if (type[to] == 1) leaves = true;
    }
    if (v != p) {
        if (!leaves) type[v] = 1;
        else type[v] = 2;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T --> 0) {
        int n;
        cin >> n;
        g.assign(n, vector<int>());
        type.assign(n, -1);
        for (int i = 0; i < n - 1; ++i) {
            int x, y;
            cin >> x >> y;
            --x; --y;
            g[x].emplace_back(y);
            g[y].emplace_back(x);
        }
        type[0] = 0;
        dfs(0, 0);
        bool root_leaf = false;
        for (auto v : g[0]) {
            if (type[v] == 1) {
                root_leaf = true;
            }
        }
        int k = 0;
        for (int i = 0; i < n; ++i) {
            k += (type[i] == 2);
        }
        cout << n - 2 * k - root_leaf << '\n';
    }
    return 0;
}

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

Если есть два вложенных отрезка, то можно оставить только меньший из них.

Как посчитать ответ для точки, если известен набор отрезков, которые к ней относятся?

К каким точкам можно отнести данный отрезок?

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

Теперь заметим, что если отрезок $$$A$$$ вложен в отрезок $$$B$$$ (т.е. $$$l_B \le l_A \le r_A \le r_B$$$), то точка, посетившая отрезок $$$A$$$, посетит и отрезок $$$B$$$. Это значит, что из всех вложенных друг в друга отрезков достаточно оставлять только те отрезки, которые не содержат в себе других отрезков.

Это можно делать с помощью дерева Фенвика. Изначально в дереве Фенвика все значения равны нулю. Будем рассматривать отрезки в порядке убывания левой границы. Пусть мы рассматриваем отрезок $$$i$$$. Если существует такой уже рассмотренный отрезок $$$j$$$, что $$$r_j \le r_i$$$, то отрезок $$$j$$$ вложен в отрезок $$$i$$$. Это так, потому что $$$l_i \le l_j$$$ из-за порядка рассматривания отрезков, и тогда $$$l_i \le l_j \le r_j \le r_i$$$. Чтобы найти количество таких $$$j$$$, достаточно узнать количество единиц на префиксе до $$$r_i$$$ в дереве Фенвика. Теперь, рассмотрев отрезок $$$i$$$, поставим в дереве Фенвика единицу на позиции $$$r_i$$$.

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

Скажем, что отрезок относится к точке, если в результате перемещения этой точки этот отрезок будет посещён. Теперь давайте научимся считать ответ для одной точки, если известен набор отрезков, которые к ней относятся. Рассмотрим те отрезки, которые лежат левее её. Из таких отрезков выберем отрезок с минимальной правой границей. Пусть расстояние от этой точки до него равно $$$a$$$. Аналогично из тех отрезков, которые лежат правее её выберем отрезок с максимальной левой границей. Пусть расстояние от этой точки до него равно $$$b$$$. Тогда ответ для этой точки равен $$$2\cdot min(a, b)+max(a, b)$$$.

Также заметим, что если отрезок лежит между двумя соседними точками, то его необходимо отнести к одной из них. (В частности, если отрезок лежит левее самой левой точки или правее самой правой, то его необходимо отнести соответственно к самой левой или самой правой точке). Теперь давайте рассмотрим отрезки, лежащие между двумя соседними точками. Они упорядочены одновременно и по левой, и по правой границе. Заметим, что какой-то префикс этих отрезков относится к левой из этих двух точек, а какой-то суффикс к правой.

Тогда давайте решать задачу с помощью динамического программирования. Пусть $$$dp[i][j]$$$ обозначает ответ, если к первым $$$i$$$ точкам мы уже отнесли отрезки, и при этом к $$$i$$$-й точке мы отнесли первые $$$j$$$ отрезков, лежащих после неё. Заметим, что всего таких состояний динамики будет линейное количество. Научимся пересчитывать эту динамику. Будем перебирать состояния в порядке увеличения $$$i$$$, а при равенстве — в порядке увеличения $$$j$$$. Пусть расстояние от $$$i$$$-й точки до $$$j$$$-го отрезка после неё равно $$$b$$$. Тогда $$$dp[i][j]=\displaystyle\min_{0 \le k \le x} \Big(dp[i-1][k]+2\cdot min(b, a_{i, k})+max(b, a_{i, k})\Big)$$$, где $$$a_{i, k}$$$ — расстояние от $$$i$$$-й точки до $$$(k+1)$$$-го отрезка после $$$(i-1)$$$-й точки, а $$$x$$$ — количество отрезков между $$$i$$$-й и $$$(i+1)$$$-й точками. Но такая динамика работает за квадрат. Тогда заметим, что для какого-то префикса отрезков после $$$(i-1)$$$-й точки $$$a_{i, k}$$$ будет больше $$$b$$$, а для какого-то суффикса меньше $$$b$$$. Длину такого префикса можно найти бинпоиском или двумя указателями. Заметим, что для $$$k$$$, принадлежащих этому префиксу, значение динамики будет равно $$$dp[i-1][k] + x_i - r_{k+1}+2\cdot b$$$, а для суффикса — $$$dp[i-1][k] + 2\cdot(x_i - r_{k+1})+b$$$. Заметим, что в этих формулах всё кроме $$$b$$$ зависит только от $$$i$$$ и $$$k$$$. Значит, мы можем быстро пересчитывать динамику с помощью префиксных и суффиксных минимумов.

Ответом будет являться $$$dp[n][x]$$$, где $$$x$$$ — количество отрезков, лежащих правее самой правой точки.

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long 

const long long INFLL = 1e18;
const int INF = 1e9 + 1;

struct segment_tree {
    vector<int> t;

    segment_tree(int n) {
        t.assign(4 * n, INF);
    }

    void mod(int v, int vl, int vr, int id, int val) {
        if (vr - vl == 1) {
            t[v] = min(t[v], val);
            return;
        }
        int vm = (vl + vr) / 2;
        if (id < vm) mod(2 * v + 1, vl, vm, id, val);
        else mod(2 * v + 2, vm, vr, id, val);
        t[v] = min(t[v], val);
    }

    int get(int v, int vl, int vr, int l, int r) {
        if (vl >= l && vr <= r) return t[v];
        if (r <= vl || l >= vr) return INF;
        int vm = (vl + vr) / 2;
        return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r));
    }
};

bool cmp(const pii &a, const pii &b) {
    return a.se - a.fi < b.se - b.fi;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<ll> a(n);
        for (auto &c : a) cin >> c;
        sort(all(a));
        vector<pii> seg1(m);
        vector<int> dl;
        for (auto &c : seg1) {
            cin >> c.fi >> c.se;
            dl.pb(c.fi);
        }
        sort(all(dl));
        dl.resize(unique(all(dl)) - dl.begin());
        sort(all(seg1), cmp);
        map<int, int> ma;
        for (int i = 0; i < (int)dl.size(); i++) ma[dl[i]] = i;
        segment_tree tr((int)dl.size());
        vector<pii> seg;
        for (auto &c : seg1) {
            int id = lower_bound(all(a), c.fi) - a.begin();
            if (id < (int)a.size() && a[id] <= c.se) continue;
            if (tr.get(0, 0, dl.size(), ma[c.fi], dl.size()) <= c.se) continue;
            tr.mod(0, 0, dl.size(), ma[c.fi], c.se);
            seg.pb(c.fi, c.se);
        }
        m = seg.size();
        sort(all(seg));
        vector<vector<pii>> g(n + 1);
        int L = -1, R = m;
        while (R - L > 1) {
            int M = (L + R) / 2;
            if (seg[M].se < a[0]) L = M;
            else R = M;
        }
        for (int i = 0; i <= L; i++) g[0].pb(seg[i]);
        for (int i = 0; i < n; i++) {
            int RIGHT = INF;
            if (i + 1 < n) RIGHT = a[i + 1];
            int id = upper_bound(all(seg), make_pair((int)a[i], (int)a[i])) - seg.begin();
            if (id == m) continue;
            int L = id - 1, R = m;
            while (R - L > 1) {
                int M = (L + R) / 2;
                if (seg[M].se < RIGHT) L = M;
                else R = M;
            }
            for (int j = id; j <= L; j++) g[i + 1].pb(seg[j]);
        }
        vector<vector<ll>> dp(n), pr(n), suff(n);
        for (int i = 0; i < n; i++) {
            dp[i].resize(g[i + 1].size() + 1, INFLL);
            pr[i].resize(g[i + 1].size() + 1, INFLL);
            suff[i].resize(g[i + 1].size() + 1, INFLL);
        }
        for (int j = 0; j <= (int)g[1].size(); j++) {
            ll x = 0;
            if (g[0].size()) x = a[0] - g[0][0].se;
            ll y = 0;
            if (j) y = g[1][j - 1].fi - a[0];
            dp[0][j] = 2 * min(x, y) + max(x, y);
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= (int)g[i].size(); j++) {
                if (j > 0) pr[i - 1][j] = pr[i - 1][j - 1];
                pr[i - 1][j] = min(pr[i - 1][j], dp[i - 1][j] - (j == (int)g[i].size() ? a[i] : g[i][j].se));
            }
            for (int j = (int)g[i].size(); j >= 0; j--) {
                if (j + 1 <= (int)g[i].size()) suff[i - 1][j] = suff[i - 1][j + 1];
                suff[i - 1][j] = min(suff[i - 1][j], dp[i - 1][j] - 2 * (j == (int)g[i].size() ? a[i] : g[i][j].se));
            }
            int L = (int)g[i].size();
            for (int j = 0; j <= (int)g[i + 1].size(); j++) {
                ll y = 0;
                if (j) y = g[i + 1][j - 1].fi - a[i];
                while (L > 0 && a[i] - g[i][L - 1].se <= y) L--;
                if (L > 0) dp[i][j] = min(dp[i][j], 2 * y + a[i] + pr[i - 1][L - 1]);
                dp[i][j] = min(dp[i][j], y + 2 * a[i] + suff[i - 1][L]);
            }
        }
        cout << dp[n - 1].back() << "\n";
    }
    return 0;
}

Ответ всегда состоит либо из трёх рёбер, имеющих один общий конец, либо из двух рёбер, не имеющих общих концов.

Для того, чтобы поддерживать ответ второго вида, в графе достаточно оставить только такие рёбра, которые входят в список трёх минимальных ребер для каждого из их концов.

Рассмотрим случаи, когда минимальное ребро входит и не входит в ответ.

Заметим, что ответ всегда состоит либо из трёх рёбер, имеющих один общий конец, либо из двух рёбер, не имеющих общих концов.

Для ответа первого вида нам достаточно поддерживать три минимальных ребра для каждой вершины.

Для того, чтобы посчитать ответ второго вида, заметим следующий факт: в графе достаточно оставить только такие рёбра, которые входят в список трёх минимальных ребер для каждого из их концов. Докажем это. Предположим, что ответ состоит из двух рёбер $$$(a, b)$$$ и $$$(c, d)$$$. Пусть есть хотя бы три ребра $$$(a, a_1)$$$, $$$(a, a_2)$$$, $$$(a, a_3)$$$, меньших, чем $$$(a, b)$$$. Тогда ребро $$$(a, b)$$$ можно заменить на одно из этих рёбер, т.к. хотя бы одно из чисел $$$a_1$$$, $$$a_2$$$, $$$a_3$$$ не равно $$$c$$$ и $$$d$$$. Тогда будем поддерживать множество всех таких рёбер.

Теперь рассмотрим два случая. Пусть $$$(a, b)$$$ — минимальное из всех рёбер. Если оно в ответе, то нам нужно найти минимальное ребро, концами которого не являются вершины $$$a$$$ и $$$b$$$. Заметим, в таком случае <<плохих>> рёбер будет не более $$$6$$$, т.к. степени каждой из вершин в графе, составленном из оставшихся рёбер, не превышают $$$3$$$. Значит, нам достаточно будет перебрать $$$O(1)$$$ вариантов. Если же $$$(a, b)$$$ не входит в ответ, то в ответ входят два ребра, концами которых являются вершины $$$a$$$ и $$$b$$$. Но таких пар рёбер не более $$$9$$$, поэтому нам опять достаточно будет перебрать $$$O(1)$$$ вариантов.

Тогда конечный ответ будет равен минимуму из ответов первого и второго видов.

#include<bits/stdc++.h>

using namespace std;

#define sz(a) (int) (a).size()

const int N = 1e5;
vector<pair<int, int>> g[N];
map<pair<int, int>, int> cost;
set<pair<int, int>> a[N], b[N];
multiset<long long> dp;
set<pair<int, pair<int, int>>> dp2;

void solve() {
    auto minr = *dp2.begin();
    long long ans = 1e18;
    if (sz(dp)) {
        ans = min(ans, *dp.begin());
    }
    int v = minr.second.first, u = minr.second.second;
    auto it = dp2.begin();
    for (int i = 0; i < 6 && it != dp2.end(); i++, it = next(it)) {
        auto res = *it;
        int v2 = res.second.first, u2 = res.second.second;
        if (v2 != v && v2 != u && u2 != v && u2 != u) {
            ans = min(ans, (long long) res.first + minr.first);
        }
    }
    for (auto [w, v2] : a[v]) {
        for (auto [w2, u2] : a[u]) {
            if (v2 != u2 && v2 != u && u2 != v) {
                ans = min(ans, (long long) w + w2);
            }
        }
    }
    cout << ans << '\n';
}

void del(int v) {
    if (sz(a[v]) >= 3) {
        long long res = 0;
        for (auto [w, to] : a[v]) {
            res += w;
        }
        dp.erase(dp.find(res));
    }
    for (auto [w, to] : a[v]) {
        if (dp2.find({w, {min(v, to), max(v, to)}}) != dp2.end()) {
            dp2.erase({w, {min(v, to), max(v, to)}});   
        }
    }
}

void upd(int v) {
    if (sz(a[v]) >= 3) {
        long long res = 0;
        for (auto [w, to] : a[v]) {
            res += w;
        }
        dp.insert(res);
    }
    for (auto [w, to] : a[v]) {
        if (a[to].find({w, v}) != a[to].end()) {
            dp2.insert({w, {min(v, to), max(v, to)}});  
        } 
    }
}

void relax(int v) {
    while (sz(a[v]) && sz(b[v])) {
        auto A = *a[v].rbegin(), B = *b[v].begin();
        if (A.first <= B.first) break;
        a[v].erase(A);
        b[v].erase(B);
        a[v].insert(B);
        b[v].insert(A);
    }
    while (sz(a[v]) < 3 && sz(b[v])) {
        auto B = *b[v].begin();
        b[v].erase(B);
        a[v].insert(B);
    }
}

void erase(int v, int u, int w) {
    del(v);
    del(u);
    if (a[v].find({w, u}) != a[v].end()) {
        a[v].erase({w, u});
    }
    else {
        b[v].erase({w, u});
    }
    if (a[u].find({w, v}) != a[u].end()) {
        a[u].erase({w, v});
    }
    else {
        b[u].erase({w, v});
    }
    relax(v);
    relax(u);
    upd(v);
    upd(u);
}

void add(int v, int u, int w) {
    del(v);
    del(u);
    b[v].insert({w, u});
    b[u].insert({w, v});
    relax(v);
    relax(u);
    upd(v);
    upd(u);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--, y--;
        if (x > y) swap(x, y);
        cost[{x, y}] = w;
        g[x].push_back({w, y});
        g[y].push_back({w, x});
    }
    for (int i = 0; i < n; i++) {
        sort(g[i].begin(), g[i].end());
        for (int j = 0; j < sz(g[i]); j++) {
            if (j <= 2) {
                a[i].insert(g[i][j]);
            }
            else {
                b[i].insert(g[i][j]);
            }
        }
        if (sz(a[i]) >= 3) {
            long long res = 0;
            for (auto [w, to] : a[i]) {
                res += w;
            }
            dp.insert(res);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < sz(g[i]); j++) {
            int v = g[i][j].second;
            if (j <= 2) {
                if (a[v].find({g[i][j].first, i}) != a[v].end()) {
                    dp2.insert({g[i][j].first, {min(i, v), max(i, v)}});
                }
            }
        }
    }
    int q;
    cin >> q;
    solve();
    while (q--) {
        int t, v, u;
        cin >> t >> v >> u;
        v--, u--;
        if (v > u) swap(v, u);
        if (t == 0) {
            int w = cost[{v, u}];
            erase(v, u, w);
        }
        else {
            int w;
            cin >> w;
            cost[{v, u}] = w;
            add(v, u, w);
        }
        solve();
    }
}

Числа с одинаковым набором простых делителей неразличимы для нас.

Количество наборов различных простых делителей, произведение которых не превосходит $$$C$$$ при данных ограничениях, не превосходит $$$\lceil 0.65 \cdot C \rceil$$$.

Как узнать $$$xor$$$ всех загаданных чисел, имеющих одинаковый набор простых делителей?

Зная $$$xor$$$ чисел с одинаковым набором простых делителей, можно рандомизированно восстановить эти числа.

Пусть $$$f(x)$$$ — произведение всех простых делителей числа $$$x$$$. Тогда давайте сделаем запросы про все такие числа $$$y$$$, что существует хотя бы одно число $$$x$$$, $$$1 \le x \le C$$$, что $$$f(x)=y$$$. При данных ограничениях таких запросов будет не более $$$\lceil 0.65 \cdot C \rceil$$$.

Сгруппируем все числа по $$$f(x)$$$. Заметим, что все числа в одной группе в любом запросе будут учтены вместе. Пусть $$$ans(x)$$$ — ответ на запрос с числом $$$x$$$, а $$$g(x)$$$ — $$$xor$$$ всех чисел, не взаимно простых с $$$x$$$. Тогда $$$g(x)=ans(x) \oplus ans(1)$$$. Тогда научимся считать $$$xor$$$ всех чисел, у которых $$$f(x)$$$ кратен заданному $$$y$$$. Для этого возьмём $$$xor$$$ всех $$$g(k)$$$, где $$$k$$$ — делитель $$$y$$$, отличный от $$$1$$$. Докажем, что таким образом мы получим нужное значение. Если $$$f(x)$$$ кратен $$$y$$$, то такой $$$x$$$ мы учтём $$$2^l-1$$$ раз, где $$$l$$$ — количество простых делителей числа $$$y$$$. Значит, такое число $$$x$$$ будет содержаться в итоговом значении. Теперь докажем, что ненужных $$$x$$$ там содержаться не будет. Пусть $$$f(x)$$$ не кратно $$$y$$$. Значит, существует такое простое число $$$p$$$, что $$$y$$$ кратно $$$p$$$, а $$$x$$$ не кратно $$$p$$$. Тогда каждому делителю $$$a$$$ числа $$$y$$$, кратному $$$p$$$, поставим в соответствие $$$b=a/p$$$. Тогда такое число $$$x$$$ либо будет учтено и для $$$a$$$, и для $$$b$$$, либо не будет учтено ни для $$$a$$$, ни для $$$b$$$. Значит, оно будет учтено чётное количество раз. Теперь, чтобы посчитать $$$xor$$$ всех чисел с заданным $$$f(x)$$$ нужно перебрать $$$x$$$ от $$$C$$$ до $$$1$$$ и сделать $$$f(x)=f(x) \oplus f(2x) \oplus f(3x) \oplus \ldots$$$.

Мы свели задачу к тому, что нужно найти $$$n$$$ различных чисел от $$$1$$$ до $$$C$$$ таких, чтобы $$$xor$$$ чисел в каждой группе был равен заданному числу. Для каждой группы чисел с заданным $$$f(x)$$$ запустим алгоритм Гаусса. Тогда пусть в группе было $$$k$$$ чисел, а после запуска осталось $$$b$$$ ненулевых чисел. Тогда если $$$b=k$$$, то у нас существует единственный способ набрать набрать заданный $$$xor$$$. Иначе у нас существует $$$2^{k-b}$$$ способов набрать заданный $$$xor$$$. Тогда давайте из них возьмём несколько случайных множеств чисел с заданным $$$xor$$$. После этого запустим рюкзак на этих числах, чтобы набрать ровно $$$n$$$ чисел. Если будет существовать несколько способов, то можно выбрать любой.

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long 
#define ld long double

const long long INFLL = 1e18;
const int INF = 1e9 + 1;
const int MAXC = 1e6;
mt19937 gen(time(0));

vector<int> e(MAXC + 5);

void precalc() {
    vector<int> p;
    for (int i = 2; i <= MAXC; i++) {
        if (e[i] == 0) {
            e[i] = i;
            p.pb(i);
        }
        for (int j = 0; j < (int)p.size() && p[j] * i <= MAXC && p[j] <= e[i]; j++) {
            e[p[j] * i] = p[j];
        }
    }
}

int f(int x) {
    int ans = 1;
    vector<int> p;
    while (x > 1) {
        p.pb(e[x]);
        x /= e[x];
    }
    for (int i = 0; i < (int)p.size(); i++) {
        if (i + 1 == (int)p.size() || p[i + 1] != p[i]) ans *= p[i];
    }
    return ans;
}

void gauss(int need, vector<int> &lst, vector<int> &ans, vector<vector<int>> &sz, vector<vector<vector<int>>> &v) {
    int n = lst.size();
    vector<bitset<20>> a(n);
    for (int i = 0; i < n; i++) a[i] = lst[i];
    bitset<20> b = need;
    vector<bitset<260>> l(n);
    for (int i = 0; i < n; i++) l[i][i] = 1;
    int i = 0;
    vector<int> col(20, -1);
    int bas_sz = 0;
    for (int j = 0; j < 20 && i < n; j++) {
        int i1 = i;
        while (i1 < n && a[i1][j] == 0) i1++;
        if (i1 == n) continue;
        swap(a[i], a[i1]);
        swap(l[i], l[i1]);
        bas_sz++;
        col[j] = i;
        for (int i2 = i + 1; i2 < n; i2++) {
            if (a[i2][j]) {
                a[i2] ^= a[i];
                l[i2] ^= l[i];
            }
        }
        i++;
    }
    bitset<20> res;
    bitset<260> path;
    for (int j = 0; j < 20; j++) {
        if (res[j] != b[j] && col[j] == -1) {
            exit(0);
        }
        if (res[j] == b[j]) continue;
        res ^= a[col[j]];
        path ^= l[col[j]];
    }
    if (a.back().count() != 0) {
        for (int i = 0; i < n; i++) {
            if (path[i]) ans.pb(lst[i]);
        }
        return;
    } 
    vector<int> diff_sz(300);
    sz.pb();
    v.pb();
    for (int it = 0; it < 100; it++) {
        bitset<260> now = path;
        for (int i = 0; i < n - bas_sz; i++) {
            if (gen() % 2) now ^= l[bas_sz + i];
        }
        int now_sz = now.count();
        if (diff_sz[now_sz]) continue;
        v.back().pb();
        for (int i = 0; i < n; i++) {
            if (now[i]) v.back().back().pb(lst[i]);
        }
        diff_sz[now_sz] = 1;
        sz.back().pb(now_sz);
    }
}

vector<int> mem(2 * MAXC + 5, -1);

int query(int x) {
    return mem[x];
}

void solve(int n, int c) {
    vector<int> calc(c + 1);
    vector<vector<int>> total(c + 1);
    for (int x = 1; x <= c; x++) total[f(x)].pb(x);
    vector<int> need;
    for (int x = 1; x <= c; x++) {
        if (total[x].size()) need.pb(x);
    }
    cout << need.size() << " ";
    for (auto &c : need) cout << c << " ";
    cout << endl;
    for (auto &c : need) {
        int x;
        cin >> x;
        mem[c] = x;
    }
    int total_xor = query(1);
    for (int x = 1; x <= c; x++) {
        if (total[x].empty()) continue;
        for (int y = x; y <= c; y += x) calc[y] ^= (query(x) ^ total_xor);
    }
    calc[1] = total_xor;
    for (int x = c; x >= 1; x--) {
        if (total[x].empty()) continue;
        for (int y = 2 * x; y <= c; y += x) {
            if (total[y].size()) calc[x] ^= calc[y];
        }
    }
    vector<int> ans;
    vector<vector<int>> sz;
    vector<vector<vector<int>>> v;
    for (int x = 1; x <= c; x++) {
        if (total[x].empty()) continue;
        gauss(calc[x], total[x], ans, sz, v);
    }
    vector<bitset<40000>> bag(sz.size() + 1);
    bag[0][0] = 1;
    for (int i = 1; i <= (int)sz.size(); i++) {
        for (auto &x : sz[i - 1]) {
            bag[i] |= (bag[i - 1] << x);
        }
    }
    int now = n - ans.size();
    for (int i = (int)sz.size(); i >= 1; i--) {
        for (int j = 0; j < (int)sz[i - 1].size(); j++) {
            int x = sz[i - 1][j];
            if (now - x >= 0 && bag[i - 1][now - x]) {
                now -= x;
                for (auto &y : v[i - 1][j]) ans.pb(y);
                break;
            }
        }
    }
    sort(all(ans));
    for (auto &c : ans) cout << c << " ";
    cout << endl;
}

int main() {
    precalc();
    int c, n;
    cin >> c >> n;
    solve(n, c);
    return 0;
}