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

#include "bits/stdc++.h"
 
using namespace std;
 
const int inf = 1e9 + 228;
 
struct SegTree {
    struct mx2node {
        pair<int, int> mx1 = {-inf, 0};
        pair<int, int> mx2 = {-inf, 0};
 
        mx2node() = default;
 
        void add(mx2node other) {
            if (other.mx1.first > mx1.first) {
                mx2 = mx1;
                mx1 = other.mx1;
            } else if (other.mx1.first == mx1.first) {
                mx1.second += other.mx1.second;
            } else if (other.mx1.first == mx2.first) {
                mx2.second += other.mx1.second;
            } else if (other.mx1.first > mx2.first) {
                mx2 = other.mx1;
            }
 
            if (other.mx2.first == mx2.first) {
                mx2.second += other.mx2.second;
            } else if (other.mx2.first > mx2.first) {
                mx2 = other.mx2;
            }
        }
    };
 
    struct node {
        int v;
        int l, r;
        int nxtl, nxtr;
        int ind_level;
        bool is_leaf;
 
        mx2node value;
        pair<int, long long> ans = {-inf, 0};
 
        node() = default;
    };
 
    static pair<int, long long> merge(pair<int, long long> a, pair<int, long long> b) {
        if (a.first == b.first) {
            return {a.first, a.second + b.second};
        }
        return max(a, b);
    }
 
    int n, k;
    vector<node> t;
    vector<vector<int>> lvl;
    vector<pair<int, int>> seg;
 
    void build_first(int v, int l, int r, int h) {
        if (lvl.size() == h) {
            lvl.emplace_back();
        }
        t[v].v = v;
        t[v].l = l, t[v].r = r;
        lvl[h].push_back(v);
        if (r - l == 1) {
            t[v].is_leaf = true;
            t[v].value = mx2node();
            t[v].ans = {-inf, 0};
            return;
        }
 
        int m = (l + r) / 2;
        build_first(v * 2 + 1, l, m, h + 1);
        build_first(v * 2, m, r, h + 1);
        t[v].is_leaf = false;
    }
 
    void calc_next(int h) {
        // v_r - v_l <= k
        int it = 0;
        auto cur = lvl[h];
        int sz = cur.size();
        for (int j = 0; j < sz; ++j) {
            auto i = cur[j];
            while (it + 1 < sz && max(abs(t[i].r - t[cur[it + 1]].l), abs(t[i].l - t[cur[it + 1]].r)) <= k) {
                ++it;
            }
            t[i].nxtr = -1;
            t[i].ind_level = j;
            if (max(abs(t[i].r - t[cur[it]].l), abs(t[i].l - t[cur[it]].r)) <= k && t[i].v != cur[it] && t[i].l != t[cur[it]].r) {
                t[i].nxtr = cur[it];
            }
        }
        it = sz - 1;
        for (int i = sz - 1; i >= 0; --i) {
            while (it - 1 >= 0 && max(abs(t[cur[i]].r - t[cur[it - 1]].l), abs(t[cur[i]].l - t[cur[it - 1]].r)) <= k) {
                --it;
            }
            t[cur[i]].nxtl = -1;
            if (max(abs(t[cur[i]].r - t[cur[it]].l), abs(t[cur[i]].l - t[cur[it]].r)) <= k && t[cur[i]].v != cur[it] && t[cur[it]].r != t[cur[it]].l) {
                t[cur[i]].nxtl = cur[it];
            }
        }
    }
 
    bool valid(const node &v, const node &u) {
        if (v.v == 1) {
            return true;
        }
        const node &a = t[v.v / 2];
        const node &b = t[u.v / 2];
        if (max(abs(b.r - a.l), abs(b.l - a.r)) <= k)
            return false;
        return true;
    }
 
    pair<int, long long> merge(const node &v, const node &u) {
        if (!valid(v, u))
            return {-inf, 0};
        if (v.v == u.v) {
            if (v.value.mx1.second > 1) {
                return {2 * v.value.mx1.first, 1ll * v.value.mx1.second * (v.value.mx1.second - 1) / 2};
            }
            return {v.value.mx1.first + v.value.mx2.first, 1ll * v.value.mx1.second * v.value.mx2.second};
        } else {
            return {v.value.mx1.first + u.value.mx1.first, 1ll * v.value.mx1.second * u.value.mx1.second};
        }
    }
 
    void update_node(node &v, int h, int first_run = 1) {
        if (!v.is_leaf) {
            v.value = mx2node();
            v.value.add(t[v.v * 2 + 1].value);
            v.value.add(t[v.v * 2].value);
        }
 
        pair<int, long long> ans = {-inf, 0};
 
        if (v.nxtr != -1) {
            ans = merge(ans, merge(v, t[v.nxtr]));
            if (t[v.nxtr].ind_level - 1 >= 0) {
                int nxt = lvl[h][t[v.nxtr].ind_level - 1];
                if (nxt != v.v) {
                    ans = merge(ans, merge(v, t[nxt]));
                }
            }
        }
        if (first_run) {
            if (v.nxtl != -1) {
                update_node(t[v.nxtl], h, false);
                if (t[v.nxtl].ind_level + 1 < (int) lvl[h].size()) {
                    int nxt = lvl[h][t[v.nxtl].ind_level + 1];
                    if (nxt != v.v) {
                        update_node(t[nxt], h, false);
                    }
                }
            }
        }
 
        if (v.r - v.l <= k) {
            ans = merge(ans, merge(v, v));
        }
 
        v.ans = ans;
        if (!v.is_leaf) {
            v.ans = merge(v.ans, t[v.v * 2 + 1].ans);
            v.ans = merge(v.ans, t[v.v * 2].ans);
        }
        if (!first_run && v.v != 1) {
            update_node(t[v.v / 2], h - 1, false);
        }
    }
 
    void update(int v, int l, int r, int pos, int value, int h = 0) {
        if (r - l == 1) {
            t[v].value = mx2node();
            t[v].value.mx1 = {value, 1};
            update_node(t[v], h);
            return;
        }
 
        int m = (l + r) / 2;
        if (pos < m) {
            update(v * 2 + 1, l, m, pos, value, h + 1);
        } else {
            update(v * 2, m, r, pos, value, h + 1);
        }
        update_node(t[v], h);
    }
 
    void update(int pos, int value) {
        update(1, 0, n, pos, value, 0);
    }
 
    SegTree(int _n, int k) : k(k) {
        int sz = 1;
        while (sz < _n) {
            sz *= 2;
        }
        n = sz;
        t.resize(2 * sz);
 
        build_first(1, 0, n, 0);
        for (int i = 0; i < (int) lvl.size(); ++i) {
            calc_next(i);
        }
    }
 
    pair<int, long long> get() {
        return t[1].ans;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    SegTree t(n, k);
    for (int i = 0; i < n; ++i) {
        t.update(i, a[i]);
    }
    pair<int, long long> ans = t.get();
    cout << ans.first << ' ' << ans.second << '\n';
    int q;
    cin >> q;
    while (q--) {
        int pos, value;
        cin >> pos >> value;
        pos = (pos + ans.first + ans.second) % n + 1;
        t.update(pos - 1, value);
        ans = t.get();
        cout << ans.first << ' ' << ans.second << '\n';
    }
}

$$$a_2 - a_1 + a_3 - a_2 + \ldots + a_n - a_{n - 1} = a_n - a_1$$$. А значит нам нужно просто максимизировать это значение, а значит ответ максимальное число в массиве минус минимальное.

Давайте заметим, что каждая клетка задевает не более двух диагоналей, поэтому ответ на задачу хотя бы $$$\frac{k + 1}{2}$$$.

Утверждение: посмотрим на конструкцию, где мы в первой строке красим все клетки. А в последней все, кроме двух боковых. Тогда каждая такая клетка соответствует ровно двум диагоналям. И если $$$k \leq (2n - 2) * 2$$$, то ответ ровно $$$\frac{k + 1}{2}$$$.

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

А значит ответ в случае $$$4n - 3$$$ такой же ввиду четности, а для $$$4n - 2$$$ это $$$\frac{k}{2} + 1$$$.

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

Также заметим, что если мы до этого проиграли суммарно $$$z$$$, то в следующий раунд нам необходимо поставить $$$y$$$ такое, чтобы $$$y \cdot (k - 1) \gt z$$$, так как иначе казино может отдать нам победу. В этом случае условие на проигрыш не более $$$x$$$ раз подряд пропадет, а мы ушли в минус. А следовательно тактика является не оптимальной.

А значит решение — мы ставим сначала $$$1$$$, затем мы ставим минимальное число, чтобы победа перекрыла наш проигрыш. И если нам хватит на $$$x + 1$$$ то такую ставку, то казино обязано уйти в минус, иначе же мы не сможем победить.

И получается решение за $$$O(x)$$$, где мы просто циклом считаем эти значения.

Пусть $$$dp_v$$$ — это количество непустых множеств вершин в поддереве $$$v$$$ таких что, нет ни одной пары вершин в множестве, где одна вершина является предком другой.

Тогда $$$dp_v = (dp_{u_1} + 1) \cdot (dp_{u_2} + 1) \cdot \ldots \cdot (dp_{u_k} + 1)$$$, где $$$u_1, \ldots, u_k$$$ — это дети вершины $$$v$$$. Так как из каждого поддерева можно выбрать либо любое непустое множество, а также пустое. А выбор из каждого поддерева пустого множества означает, что выбрали единственную вершину $$$v$$$. (так как в нашей динамике не может быть пустого множества).

Теперь утверждение: ответ на задачу это $$$dp_1 + dp_2 + \ldots + dp_n + 1$$$. Так как если мы говорим, что пусть у нас есть пара вершин, где вершина $$$v$$$ является предком другой. Тогда ответ в этом случае это $$$dp_{u_1} + \ldots + dp_{u_k}$$$, так как мы можем выбрать ровно из одного поддерева такое множество вершин из динамики. (И как раз здесь мы используем непустые множества в состоянии динамики, ибо иначе учитывался вариант, где одна нет вершин, где одна предок другой). А $$$dp_1 + 1$$$ (где $$$1$$$ — это корень дерева) отвечает за варианты, где нет вершины, где одна вершина является предком другой.

Давайте для каждого ребра $$$i$$$ отметим множество пар $$$S_i$$$, которое оно перекрывает. Тогда утверждение: У нас различных множеств $$$O(k)$$$. Так как нас интересуют только ребра, которые находятся в сжатом дереве на этих $$$k$$$ пар вершин. А как известно, ребер в сжатом дереве $$$O(k)$$$.

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

Пусть $$$dp[mask]$$$ — это минимальное количество ребер, которые нужно удалить, чтобы были в парах соответсвующим единичным битам из $$$mask$$$ было вычеркнуто хотя бы одно ребро.

Тогда пересчет следующий $$$dp[mask | S_i] = min(dp[mask | S_i], dp[mask] + 1)$$$ по всем различным множествам $$$S$$$, где $$$S_i$$$ это маска соответсвующая парам, которые проходят через ребро. А пересчет такой, так как мы к этой маске добавляем еще одно ребро.

В итоге получаем решение за $$$O(nk + 2^k k)$$$, где за $$$O(nk)$$$ мы для каждого ребра предпосчитываем множество пар, которое оно вычеркивает, а $$$O(2^k k)$$$ это пересчет динамики.

Давайте выпишем номера вершин в порядке их значений. Пусть это $$$v_1, \ldots, v_n$$$. Тогда должно выполняться $$$value_{v_i} \leq value_{v_{i + 1}}$$$.

Тогда у нас есть некоторые отрезки в этом порядке, для которых нам значения не известны. Тогда нам для каждого отрезка известно максимальное и минимальное значение, которое могут принимать значения на этом отрезке, пусть это $$$L$$$ и $$$R$$$. Тогда нам нужно для каждого числа на этом отрезке выбрать значение из отрезка $$$(L, R)$$$, чтобы сохранялся относительный порядок. А это известная задача и таких вариантов $$$\binom{R - L + len}{len}$$$, где $$$len$$$ это размер отрезка. А затем нужно перемножить все эти биноминальные коеффициенты.

Теперь заметим, что у нас $$$R - L + len$$$ большое, поэтому для подсчета можно просто воспользоваться формулой $$$\binom{n}{k} = \frac{n \cdot (n - 1) \cdot \ldots \cdot (n - k + 1)}{k!}$$$, так как сумма $$$len$$$ не превосходит $$$n$$$.

У нас могут быть только следующие пары чисел $$$(x, x)$$$, $$$(x, 2 \cdot x)$$$, $$$(x, 3 \cdot x)$$$

Давайте заметим, что у нас могут быть только следующие пары чисел: $$$(x, x)$$$, $$$(x, 2 \cdot x)$$$, $$$(x, 3 \cdot x)$$$.

Количество первого типа $$$n$$$, второго $$$2 \cdot \lfloor \frac{n}{2} \rfloor$$$, третьего $$$2 \cdot \lfloor \frac{n}{3} \rfloor$$$. А значит, ответ на задачу равен $$$n + 2 \cdot \left( \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor \right)$$$.

Решите эту задачу для $$$k = 2$$$.

Решите задачу, когда нет ограничения на закрашенную клетку.

Попытайтесь закрашивать клетки по диагоналям.

Если в вашем коде много строчек не пишите)

Давайте заметим, что ответ на задачу не меньше $$$\frac{n^2}{k}$$$, так как квадрат можно разбить на непересекающиеся подпрямоугольники размера $$$1 \times k$$$. Значит нужно научиться делать пример на это число.

Решим вначале задачу, без ограничения на закрашенную клетку. Тогда нам хочется сделать что-то типа шахматной расскраски, то есть диаганальную раскраску.

В этом случае, мы можем пронумеравать диаганали (от самой "нижней", до самой "верхней"). В этом случае в каждом подпрямоугольнике будет $$$k$$$ подряд идущих диагоналей, а значит, если закрасить каждую $$$k$$$ диаганаль, то мы получим ответ на задачу (и ответ в точности будет равен $$$\frac{n^2}{k}$$$, так как в каждом подпрямоугольнике мы закрасили ровно одну клетку).

Ну а можно заметить, что клетка $$$(x, y)$$$ принадлежит диагонале с номером $$$x + y$$$. (Так как когда мы идем на одну клетку вверх-влево, то одна из координат увеличивается на 1, а другая не меняется). А значит, нужно просто закрасить все клетки, у которых $$$(x + y) \% k = (a + b) \% k$$$

Если $$$b_{i} \gt b_{i + 1} + 1$$$, то могут быть проблемы

Все нормально, если $$$a_i = b_i$$$

Программист не математик, можно не доказывать решение.

Очевидно, что для любого $$$i$$$ должно выполняться, что либо $$$a_i = b_i$$$, либо $$$b_i \leq b_{i + 1} + 1$$$, так как либо $$$a_i$$$ уже равно $$$b_i$$$ и $$$i$$$ элемент увеличивать не нужно, либо же мы должны увеличить $$$a_i$$$ до $$$b_i$$$ операциями из условия, а на них накладываются ограничения выше.

Теперь докажем, что этих двух условий достаточно. Пусть $$$i$$$ — это индекс минимального элемента в $$$a$$$, который не равен $$$b_i$$$. Тогда заметим, что мы в любом случае сможем сделать $$$a_i := a_i+1$$$, так как в этом случае выполняется $$$a_i \leq b_i \leq b_{i + 1} + 1$$$, а значит можно увеличить $$$a_i$$$. То есть такими операциями можно получить массив $$$b$$$.

Переформулируйте чуть лучше задачу в терминах полного бинарного дерева.

Странно на одной и той же глубине делать два изменения.

Давайте поймем, что задачу можно переформулировать следующим образом: Дано полное бинарное дерево с $$$2^n$$$ листами. Также для каждой вершины, не являющейся листом, помечено ребро в ровно одного из детей. А ответ на задачу — это лист, до которого можно добраться из корня по отмеченным ребрам. А изменения — это сменить помеченное ребро выходящее из вершины.

Тогда понятно, что нет смысла делать изменения больше, чем у одной вершины на уровне, так как нам важна только одна вершина, до которой идет путь, а значит ответ зависит только от того, на каких глубинах мы решили поменять исход (и очевидно, что разные множества изменненых исходов дают разного победителя). А значит если $$$k$$$ фиксированно — $$$\binom{n}{k}$$$ (так как нам нужно просто выбрать, какие из $$$k$$$ глубин мы будем изменять), а значит ответ на задачу равен $$$\sum{\binom{n}{i}}$$$, где $$$0 \leq k \leq min(n, k)$$$.

Перебирите $$$c$$$

$$$gcd(a, b)$$$ является делителем числа $$$a + b$$$.

Вспомните о существовании функции эйлера

Давайте будем перебирать $$$c$$$, тогда $$$gcd(a, b) = gcd(a, a + b) = gcd(a, n - c)$$$. Значит $$$gcd(a, b)$$$ являются делителем числа $$$n - c$$$. Давайте тогда переберем все делители числа $$$n - c$$$. Пусть $$$d$$$ является делителем, тогда количество пар чисел $$$a, b$$$, где $$$a + b = n - c$$$ и $$$gcd(a, b) = d$$$ равно $$$\phi (\frac{n - c}{d})$$$, так как нам нужно $$$a$$$ кратное $$$d$$$ и при этом оно должно быть простым с $$$\frac{n - c}{d}$$$, чтобы $$$gcd$$$ был в точности равен $$$d$$$.

А значит ответ на задачу равен $$$\sum{lcm(c, d) * \phi{\frac{n - c}{d}}}$$$, где $$$1 \leq c \leq n - 2$$$, а $$$d$$$ делит $$$n - c$$$

#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = (1 << 19);
 
pair<int, int> t[2 * N]; // сnt, maximum
int mod[2 * N];
bool its_leaf[2 * N];
 
void push(int v) {
    t[v * 2 + 1].second += mod[v];
    t[v * 2].second += mod[v];
    mod[v * 2 + 1] += mod[v];
    mod[v * 2] += mod[v];
    mod[v] = 0;
}
 
int f(int v, int w) {
    if (its_leaf[v]) {
        if (t[v].second > w)
            return 1;
        return 0;
    }
 
    push(v);
    int r = v * 2, l = v * 2 + 1;
    if (t[l].second >= w)
        return f(r, w);
    else
        return f(l, w) + t[v].first - t[l].first;
}
 
void update(int v, int l, int r, int L, int R, int val) {
    if (R <= l || r <= L)
        return;
    if (L <= l && r <= R) {
        t[v].second += val;
        mod[v] += val;
        return;
    }
 
    push(v);
    int m = (l + r) / 2;
    update(v * 2 + 1, l, m, L, R, val);
    update(v * 2, m, r, L, R, val);
    t[v].first = t[v * 2 + 1].first + f(v * 2, t[v * 2 + 1].second);
    t[v].second = max(t[v * 2 + 1].second, t[v * 2].second);
}
 
void build(int v, int l, int r, vector<int> &a) {
    if (r - l == 1) {
        its_leaf[v] = 1;
        t[v] = make_pair(1, a[l]);
        return;
    }
 
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m, a);
    build(v * 2, m, r, a);
    t[v].first = t[v * 2 + 1].first + f(v * 2, t[v * 2 + 1].second);
    t[v].second = max(t[v * 2 + 1].second, t[v * 2].second);
}
 
pair<int, int> get(int v, int l, int r, int L, int R, int max_val) { // ans, max_val
    if (R <= l || r <= L)
        return {0, max_val};
    if (L <= l && r <= R)
        return {query(v, max_val), max(t[v].second, max_val)};
 
    push(v);
    int m = (l + r) / 2;
    auto z1 = get(v * 2 + 1, l, m, L, R, max_val);
    auto z2 = get(v * 2, m, r, L, R, z1.second);
    return {z1.first + z2.first, max(z1.second, z2.second)};
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int q;
    cin >> q;
    build(1, 0, n, a);
 
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            cout << get(1, 0, n, l - 1, r, -n).first << '\n';
        } else {
            int val;
            cin >> val;
            update(1, 0, n, l - 1, r, val);
        }
    }
}

В оптимальном ответе максимальное количество цифр, так что нужно использовать только цифры $$$1,2$$$.

Чередуйте эти цифры, чтобы не было соседних одиннаковых цифр.

Так как мы хотим максимизировать нужное нам число, найдем сначало самое длинное подходящее число. Очевидно, что для этого лучше использовать только цифры $$$1$$$ и $$$2$$$. Поэтому ответ всегда имеет вид $$$2121\ldots$$$ или $$$1212\ldots$$$. Первый вариант оптимален, когда $$$n$$$ имеет остаток $$$2$$$ или $$$0$$$ по модулю $$$3$$$, в противном случае оптимален второй вариант.

Ниже приведен пример аккуратной реализации.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    int type;
    if (n % 3 == 1)
        type = 1;
    else
        type = 2;
    int sum = 0;
    while (sum != n) {
        cout << type;
        sum += type;
        type = 3 - type;
    }
    cout << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Что представляет собой картинка, если ответ на задачу "YES".

Подумайте над квадратом размера $$$2 \times 2$$$.

Заметим, что ответ на задачу "YES" тогда и только тогда, когда картинка предствляет из себя какое-то количество непересекающихся прямоугольников. Теперь посмотрим в этом случае на все квадраты размера $$$2 \times 2$$$, заметим, что в каждом из них не может быть ровно $$$3$$$ закрашенных клетки.

Также понятно, что если найдутся $$$3$$$ таких клетки, то найдутся два пересекающихся прямоугольника. Поэтому нужно просто проверить, есть ли квадрат $$$2 \times 2$$$, в котором ровно $$$3$$$ закрашенных клетки.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int> (m));
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j) {
            a[i][j] = s[j] - '0';
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            int sum = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
            if (sum == 3) {
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Ответ всегда есть, когда правая верхняя клетка покрашена в белый цвет.

Представьте, что у вас есть только прямоугольники размера $$$1 \times 2$$$.

Закрашивайте клетки с "конца".

По условию, если левая верхняя клетка покрашена в черный цвет, то мы не можем так покрасить. Иначе можно. Давайте будем красить клетки в следующем порядке: $$$(n, m), (n, m - 1), \ldots, (n, 1), (n - 1, m), \ldots (1, 1)$$$.

Пусть клетку $$$(i, j)$$$ нужно покрасить в черный цвет, тогда если $$$j \gt 1$$$, то просто покрасим прямоугольник $$$(i, j - 1)$$$, $$$(i, j)$$$. Иначе, если $$$j = 1$$$, то мы покрасим прямоугольник $$$(i - 1, j)$$$.

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

Таким образом мы умеем красить таблицу за максимум $$$n \cdot m - 1$$$ операций.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int> (m));
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j)
            a[i][j] = s[j] - '0';
    }
    vector<array<int, 4>> ans;
    if (a[0][0] == 1) {
        cout << -1<< '\n';
        return;
    }
    
    for (int j = m - 1; j >= 0; --j) {
        for (int i = n - 1; i >= 0; --i) {
            if (a[i][j]) {
                if (i != 0) {
                    ans.push_back({i, j + 1, i + 1, j + 1});
                } else {
                    ans.push_back({i + 1, j, i + 1, j + 1});
                }
            }
        }
    }
    cout << ans.size() << '\n';
    for (auto i : ans) {
        cout << i[0] << ' ' << i[1] << ' ' << i[2] << ' ' << i[3] << '\n';
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Число красивое только в том случае, если оно кратно $$$d$$$, но не кратно $$$d^2$$$

Давайте решим более общую задачу: посчитать количество таких разбиений.

Эта задача решается динамическим программированием.

Храните в динамике оставшееся число, а также последний делитель.

Давайте решим более сложную задачу: посчитать количество разбиений на такие множители.

Заметим, что это несложно решается диническим программированием. Пусть $$$dp_{n, d}$$$ — количество разложений на множители, если у нас осталось число разложить число $$$n$$$, а до этого мы поделили на число $$$d$$$. Перебирем все такие красивые числа $$$i \geq d$$$, которые делят $$$n$$$, тогда $$$dp_{n / i, i} += dp_{n, d}$$$.

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

Пусть $$$C$$$ — это количество делителей числа $$$x$$$, а $$$V$$$ — это количество красивых делителей числа $$$x$$$. Тогда это работает за $$$O(С \cdot V)$$$ или $$$O(C \cdot V^2 \cdot log)$$$ в зависимости от реализации (так как $$$n$$$ всегда является делителем числа $$$x$$$), но все это легко заходит, так как $$$V$$$ не больше (посчитать максимальное значение).

#include <bits/stdc++.h>
 
using namespace std;
 
bool good(int i, int d) {
    return i % d == 0 && i % (1ll * d * d) != 0;
}
 
void solve() {
    int x, d;
    cin >> x >> d;
    map<pair<int, int>, int> dp;
    dp[{x, 1}] = 1;
    int res = 0;
    vector<int> del;
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            if (good(i, d))
                del.push_back(i);
            if (x != i * i && good(x / i, d))
                del.push_back(x / i);
        }
    }
    while (dp.size()) {
        auto z = *dp.rbegin();
        if (z.first.first == 1) {
            res += z.second;
        }
        for (auto i : del) {
            if (z.first.first % i == 0 && i >= z.first.second) {
                dp[{z.first.first / i, i}] = min(dp[{z.first.first / i, i}] + z.second, 2);
            }
        }
        dp.erase(z.first);
    }
    if (res == 1)
        cout << "NO\n";
    else
        cout << "YES\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Рассмотрим случаи

Пусть $$$x = d^a \cdot b$$$. Где $$$b$$$ не кратно $$$d$$$.

Тогда рассмотрим несколько случаев:

• $$$a = 1$$$. Тогда $$$a$$$ — это красивое число, поскольку любое число кратное $$$d^2$$$ можно разложить на $$$d \cdot (a / d)$$$, каждое из которых красиове, а число кратное только $$$d$$$, очевидно, разложить нельзя. Значит в этом случае ровно один вариант.

• $$$b$$$ — составное, тогда, очевидно, мы можем разложить несколькими вариантами, если $$$a \neq 1$$$.

• $$$d$$$ — простое. Если $$$b$$$ простое, то утверждение — у нас только один вариант разложить число. Так как каждый красивый множитель вида $$$d \cdot k$$$. Но поскольку $$$d$$$ простое, то никаких других способов разложить нет, кроме как добавить множитель из $$$b$$$, а поскольку $$$b$$$ простое, то все эти варианты будут равны до перестановки.

• $$$d$$$ — составное и не является степенью простого. Если $$$a \leq 2$$$, то этот случай никак не отличается от прошлого, так как мы все равно должны получить два красивых множителя и все они будут просто равны $$$d$$$. Иначе пусть $$$d = p \cdot q$$$, где $$$gcd(p, q) = 1$$$. Тогда мы можем сделать число $$$p \cdot q^{b - 1}$$$ и $$$p^{b - 1} \cdot q$$$. А также $$$q \cdot p, q \cdot p, \ldots , q \cdot p$$$, в этом случае у нас разное количество делителей, так что эти варианты будут разные, а значит у нас несколько вариантов в этом случае.

• $$$d$$$ — степень простого числа. Тогда $$$d = p^k$$$. Утверждение, если $$$d = p^2$$$, а $$$x = p^7$$$, то нельзя разложить несколькими способами, иначе, если $$$a \gt 2$$$ и $$$k \gt 1$$$, то посмотрим на разбиение $$$p^{2k - 1}, p^{k + 1}, p^k, \ldots , p^k$$$, понятно, что если $$$k \gt 2$$$, то даже если $$$b = p$$$, то множитель $$$p^{k + 2}$$$ до сих пор будет красивым, поэтому это не отличается от составного $$$d$$$ в прошлом случае. Иначе, если $$$k = 2$$$, то если $$$a = 3$$$ и $$$b = p$$$, то ничего добавить нельзя, а иначе у нас будет возможность выбрать $$$3$$$ множителя $$$p^k$$$, а остальное как-то разложить (так как в этом случае $$$a \gt 3$$$, то хотя бы еще один множитель будет) и добавить туда $$$b$$$. А эти 3 множителя мы можем разложить на $$$2$$$ или $$$3$$$ множителя, как написано выше. Поэтому единственный уникальный случай, когда $$$d$$$ — степень простого, это $$$d = p^2, x = p^7$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int prime(int x) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0)
            return i;
    }
    return -1;
}
 
void solve() {
    int x, d;
    cin >> x >> d;
    int cnt = 0;
    while (x % d == 0) {
        ++cnt;
        x /= d;
    }
    if (cnt == 1) {
        cout << "NO\n";
        return;
    }
    if (prime(x) != -1) {
        cout << "YES\n";
        return;
    }
    if (prime(d) != -1 && d == prime(d) * prime(d)) {
        if (x == prime(d) && cnt == 3) {
            cout << "NO\n";
            return;
        }
    }
    if (cnt > 2 && prime(d) != -1) {
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--)
        solve();
}

После каждой операции максимальный номер всегда увеличивается на конкретное число.

Ученики с номером большим $$$n$$$ нас не интересуют.

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

Поймите, что каждый школьник после всех операций перейдет за одну конкретную парту.

Напишите жадник

После каждого урока номер человека с максимального номера увеличивается на количество парт, куда никто не переходит. Поэтому можно легко вычислить сколько прошло времени с самого начала, пусть это число $$$k$$$.

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

Пусть $$$to_i$$$ — это парта, в которую перейдет школьник после $$$k$$$ пересадок, изначально сидевший за $$$i$$$ партой. Это стандартная задача, которую можно решить при помощи бинарный подъемов или не самого приятного dfs c выделением циклов и подобным. (но последнее мы не рекомендуем вам писать), Определим множество $$$V_i$$$, как множество всех чисел $$$j$$$, где $$$to_j = i$$$.

Пусть стартовая расстановка школьника — это перестановка $$$b$$$, тогда поймем, что если за $$$i$$$ парту кто-то пересаживается после $$$k$$$ операций, то значение в ней это — минимальное значение в $$$V_i$$$. А если за нее никто не пересаживается, то в ней просто будет всегда сидеть школьник с одиннаковым номером, вне зависимости от начальной рассадки. После этого не сложно покзаать оптимальную стартовую рассадку школьников.

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

Если мы знаем, что существует парта, для которой должно выполняться $$$min(V_i) = i$$$, то мы должны посадить за $$$i$$$ парту школьника с минимальным номером из $$$V_i$$$, а оставшихся людей мы можем садить за любые парты с номером большим $$$i$$$, поэтому добавим в множество $$$s$$$ всех остальных школьников. А иначе нам нужно просто взять человека из $$$s$$$ с минимальным номером и посадить его за место под номером $$$i$$$, а затем просто удалить его из множества $$$s$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
const int K = 30;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<int> cnt(n);
    vector<vector<int>> up(n, vector<int> (K));
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        --a;
        ++cnt[a];
        up[i][0] = a;
    }
    for (int k = 1; k < K; ++k) {
        for (int i = 0; i < n; ++i) {
            up[i][k] = up[up[i][k - 1]][k - 1];
        }
    }
    vector<int> a(n);
    int cnt_bad = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (!cnt[i]) {
            ++cnt_bad;
        }
    }
    int k = (*max_element(a.begin(), a.end()) - n) / cnt_bad;
    vector<vector<int>> add(n);
 
    for (int i = 0; i < n; ++i) {
        int v = i, level = k;
        for (int j = K - 1; j >= 0; --j) {
            if (level >= (1 << j)) {
                level -= (1 << j);
                v = up[v][j];
            }
        }
        add[a[v] - 1].push_back(i);
    }
    set<int> now;
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        if (add[i].size()) {
            int res = *min_element(add[i].begin(), add[i].end());
            for (int j : add[i]) {
                if (j != res) {
                    now.emplace(j);
                }
            }
            ans[res] = i + 1;
        } else {
            ans[*now.begin()] = i + 1;
            now.erase(*now.begin());
        }
    }
    for (int i : ans)
        cout << i << ' ';
    cout << '\n';
}

Осознайте, что максимальный элемент всегда является "перегибом" первой последовательности.

Можно предположить, что "перегиб" второй подпоследовательности всегда будет левее максимального элемента (если что, можно будет потом просто развернуть массив).

Всего у нас существует $$$3$$$ момента времени — обе подпоследовательности возрастают, первая убывает, а вторая возрастает, или обе подпоследовательности убывают.

Первый и третий случай решаются очевидной жадностью.

Для второго можно просто написать динамику.

Перегиб последовательности — это максимальное число в подпоследовательности. Тогда заметим, что в первой подпоследовательности перегибом будет максимальное число в нашем массиве, пусть его позиция в массиве — $$$ind$$$.

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

В этом случае у нас будет $$$3$$$ состояния: обе подпоследовательности возрастают, первая убывает, а вторая возрастает или обе подпоследовательсности убывают.

Решим для начала первый случай:

Пусть $$$dp1_i$$$ — минимально возможный максимальный элемент в подпоследовательности, которая не содержит $$$i$$$ элемент. Она считается не сложно. Если $$$dp1_{i - 1} \lt a_{i}$$$, то $$$dp1_{i} = min(dp1_{i}, a_{i - 1})$$$, так как в этом случае мы можем добавить $$$i$$$ элемент в подпоследовательность, которая не содержит элемент $$$i - 1$$$. Аналогично, если $$$a_{i - 1} \lt a_{i}$$$, то $$$dp1_{i} = min(dp1_{i}, dp1_{i - 1})$$$.

Третий случай считается анологично, но только его нужно считать с конца. (Этот массив будет $$$dp3$$$)

Теперь разберемся со вторым случаем:

Пусть $$$dp2_{i, 0}$$$ — минимально возможный последний элемент во второй подпоследовательности, если $$$i$$$ элемент принадлежит первой подпоследовательности. И $$$dp2_{i, 1}$$$ — максимально возможный последний элемент в первой подпоследовательности, если $$$i$$$ элемент принадлежит второй подпоследовательности. Есть несколько вариантов. Если $$$i$$$ и $$$i - 1$$$ лежат в одинаковых и разных подпоследовательностях. И мы будем считать для $$$i \leq ind$$$, поскольку до этого участка обе подследовательности возрастают, а это уже другой посчитанный случай. И тогда не сложно получить формулы пересчета:

• $$$dp2_{ind, 0} = dp1_{ind}$$$, по определению $$$dp2_{ind, 0}$$$
• Если $$$a_{i - 1} \gt a_i$$$, то $$$dp2_{i, 0} = min(dp2_{i, 0}, dp2_{i - 1, 0})$$$.
• Если $$$dp2_{i - 1, 1} \gt a_i$$$, то $$$dp2_{i, 0} = min(dp2_{i, 0}, a_{i - 1})$$$.
• Если $$$a_{i - 1} \lt a_{i}$$$, то $$$dp2_{i, 1} = max(dp2_{i, 1}, dp3_{i - 1, 1})$$$.
• Если $$$dp2_{i - 1, 0} \lt a_i$$$, то $$$dp2_{i, 1} = max(dp2_{i, 1}, a_{i - 1})$$$.

Теперь поймем, что элемент с номером $$$i$$$ может быть перегибом второй подпоследовательности, если $$$i \gt ind$$$, а также $$$dp2_{i, 1} \gt dp3_{i}$$$. То есть мы можем перейти из второго состояния в третье.

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 1e9 + 228;
 
int solve (int n, vector<int> a) {
    int ind = max_element(a.begin(), a.end()) - a.begin();
    vector<int> dp1(n, inf);
    dp1[0] = -1;
    for (int i = 1; i <= ind; ++i) {
        if (a[i] > dp1[i - 1])
            dp1[i] = min(dp1[i], a[i - 1]);
        if (a[i] > a[i - 1])
            dp1[i] = min(dp1[i], dp1[i - 1]);
    }
 
    vector<int> dp2(n, inf);
    dp2[n - 1] = -1;
    for (int i = n - 2; i >= ind; --i) {
        if (a[i] > dp2[i + 1])
            dp2[i] = min(dp2[i], a[i + 1]);
        if (a[i] > a[i + 1])
            dp2[i] = min(dp2[i], dp2[i + 1]);
    }
 
    vector<array<int, 2>> dp3(n, {inf, -inf});
    dp3[ind][0] = dp1[ind];
    int ans = 0;
    for (int i = ind + 1; i < n; ++i) {
        if (a[i - 1] > a[i])
            dp3[i][0] = min(dp3[i][0], dp3[i - 1][0]);
        if (dp3[i - 1][1] > a[i])
            dp3[i][0] = min(dp3[i][0], a[i - 1]);
        
        if (a[i - 1] < a[i])
            dp3[i][1] = max(dp3[i][1], dp3[i - 1][1]);
        if (dp3[i - 1][0] < a[i])
            dp3[i][1] = max(dp3[i][1], a[i - 1]);
        
        if (dp3[i][1] > dp2[i])
            ++ans;
    }
    return ans;
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int ans = solve(n, a);
    reverse(a.begin(), a.end());
    cout << ans + solve(n, a) << '\n';
}