Давайте покажем конструкцию, которая максимизирует количество лайков. Нам нужно сначала оставить все лайки, которые мы можем поставить, а только потом убирать их.

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

Приведенный ниже код реализует эти конструкции.

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;
    cin >> n;
    int likes = 0, dislikes = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) likes++;
        else dislikes++;
    }
    for (int i = 1; i <= n; ++i) {
        if (i <= likes) cout << i << ' ';
        else cout << likes * 2 - i << ' ';
    }
    cout << '\n';

    for (int i = 1; i <= n; ++i) {
        if (i <= dislikes * 2) cout << i % 2 << ' ';
        else cout << (i - dislikes * 2) << ' ';
    }
    cout << '\n';
}

signed main() {
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve();
    }
    return 0;
}

Todo

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    int known = 0, unknown = 0;
    int need = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x == 1) ++unknown;
        else {
            known += unknown;
            unknown = 0;
        }
        need = max(need, unknown + (known ? known / 2 + 1 : 0));
    }
    cout << need << endl;
}

signed main() {
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

Максимальное количество различных чисел, которые мы можем набрать, всегда равно $$$n \cdot m$$$. Покажем, как можно построить пример для любых $$$n$$$ и $$$m$$$.

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

Возьмем $$$N = M = 2^8$$$ и построим матрицу следующим алгоритмом. Разобьем её на блоки размера $$$2 \times 2$$$. Пронумеруем блоки слева направо и сверху вниз по порядку, начиная с нуля. $$$i$$$-й блок будет иметь вид

$$$4i + 0$$$ $$$4i + 1$$$

$$$4i + 2$$$ $$$4i + 3$$$

При таком построении побитовое исключающее ИЛИ любой подматрицы размера $$$2 \times 2$$$ будет равно нулю. Убедиться в этом можно следующим образом. Посмотрим на левый верхний угол $$$(i, \, j)$$$ произвольной подматрицы размера $$$2 \times 2$$$. Есть 4 случая:

1. обе координаты четные;
2. $$$i$$$ четная, $$$j$$$ нечетная;
3. $$$i$$$ нечетная, $$$j$$$ четная;
4. обе координаты нечетные.

Сразу отметим, что $$$i, \, j < 200 < 2^8$$$

Рассмотрим самый неприятный случай — последний. Остальные случаи рассматриваются аналогичным способом. В таком случае подматрица будет иметь вид:

$$$4i + 3$$$ $$$4(i + 1) + 2$$$

$$$4(i + 2^8) + 1$$$ $$$4(i + 2^8 + 1) + 0$$$

Заметим, что вторая часть каждого слагаемого меньше 4, а первая часть каждого слагаемого больше или равна 4. Поэтому их можно рассматривать независимо.

$$$3 \oplus 2 \oplus 1 \oplus 0$$$ $$$=$$$ $$$0$$$.

Если $$$i$$$ $$$=$$$ $$$1$$$, то

$$$4i \oplus 4(i + 1)$$$ $$$=$$$ $$$12$$$,

$$$4(1 + 2^8) \oplus 4(2 + 2^8)$$$ $$$=$$$ $$$12$$$.

Если $$$i \neq 1$$$, то

$$$4i \oplus 4(i + 1)$$$ $$$=$$$ $$$4$$$

$$$4(i + 2^8) \oplus 4(i + 2^8 + 1)$$$ $$$=$$$ $$$4$$$ (при $$$i=0$$$ можно проверить руками, при $$$1 < i < 2^8$$$ $$$4(i + 2^8)$$$ сократятся и от второго слагаемого останется $$$4$$$).

$$$4 \oplus 4 \oplus 0$$$ $$$=$$$ $$$0$$$. Таким образом, в выбранной подматрице побитовое исключающее ИЛИ равно нулю.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int SZ = 256;

int v[SZ][SZ];

void Solve(){
    int n, m;
    cin >> n >> m;

    cout << n * m << '\n';

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cout << v[i][j] << " \n"[j + 1 == m];
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    {
        int now = 0;
        int n = 256;
        int m = 256;

        for(int i = 0; i < n; i += 2)
            for(int j = 0; j < m; j += 2){
                v[i][j] = now;
                v[i][j + 1] = now + 1;
                v[i + 1][j] = now + 2;
                v[i + 1][j + 1] = now + 3;
                now += 4;
            }
    }

    int num_test = 1;
    cin >> num_test;

    for(int i = 1; i <= num_test; i++){
        Solve();
    }
}

Для начала отсортируем все отделы по убыванию $$$b_i$$$ (а при равенстве~--- по возрастанию $$$a_i$$$). Теперь переберем отдел $$$i$$$, в котором будет куплен самый дорогой подарок для второй подруги. Заметим, что во всех отделах с номерами $$$j < i$$$, Саша должен купить подарок для первой подруги, иначе подарок $$$i$$$ не будет обладать максимальной стоимостью среди подарков, купленных для второй подруги. Поэтому сразу найдем значение $$$m = \max \limits_{j < i} a_j$$$. Таким образом, мы уже можем получить ответ $$$\lvert m - b_i \rvert$$$.

Во всех отделах с номерами $$$j > i$$$, для которых $$$a_j \le m$$$, Саша может купить подарок для любой из подруг, и это никак не повлияет на ответ. Теперь рассмотрим все отделы с номерами $$$j > i$$$, для которых $$$a_j > m$$$. Если в некотором из подобных отделов купить подарок для первой подруги, то значение $$$m$$$ увеличится, а значит ответ может улучшиться. Поэтому переберем все таким отделы и обновим ответ значением $$$\lvert a_j - b_i \rvert$$$.

Время работы: $$$O(n^2)$$$.

Давайте оптимизируем это решение. Для начала вместо того, чтобы вычислять величину $$$m$$$ на каждой итерации заново, будем поддерживать ее значение в некоторой переменной. Тогда при переходе от отдела $$$i - 1$$$ к отделу $$$i$$$ будем обновлять значение $$$m$$$ следующим образом: $$$m := \max(m, a_i)$$$.

Осталось научиться быстро находить оптимальный номер отдела $$$j$$$, такой что $$$j > i$$$, $$$a_j > m$$$, а также $$$\lvert a_j - b_i \rvert$$$ минимально. Выберем на суффиксе массива минимальное $$$a_j$$$, такое что $$$a_j \ge b_i$$$, а также максимальное $$$a_j$$$, такое что $$$a_j \le b_i$$$. Можно заметить, что оптимальным $$$a_j$$$ является одно из двух выбранных чисел (нужно также не забыть проверить условие $$$a_j > m$$$). Поэтому, достаточно обновить ответ только при помощи них.

Искать данные два элемента можно, используя структуру данных \texttt{set}. Будем поддерживать в множестве все $$$a_j$$$, находящиеся на суффиксе. Тогда можно найти нужные два элемента за $$$O(\log n)$$$. При переходе от отдела $$$i - 1$$$ к отделу $$$i$$$ нужно удалить значение $$$a_{i - 1}$$$ из структуры данных.

Время работы $$$O(n \log n)$$$

#include <bits/stdc++.h>

using namespace std;

template<typename T>
bool smin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool smax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int INF = 0x3f3f3f3f;
const int N = 500100;

std::pair<int, int> a[N];

void run() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &a[i].first, &a[i].second);
    }

    sort(a, a + n, [&](const pair<int, int>& p1, 
                            const pair<int, int>& p2) {
        return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);
    });

    multiset<int> setik;
    for (int i = 0; i < n; ++i) {
        setik.insert(a[i].first);
    }

    int mx = -INF;
    int ans = INF;
    
    for (int i = 1; i < n; ++i) {
        smin(ans, abs(a[i].first - a[0].second));
    }
    
    for (int i = 0; i < n; ++i) {
        setik.erase(setik.find(a[i].first));
        if (i == 0) {
            mx = a[i].first;
            continue;
        }

        smin(ans, abs(mx - a[i].second));
        auto it = setik.lower_bound(a[i].second);
        if (it != setik.end() && *it >= mx) {
            smin(ans, abs(*it - a[i].second));
        }
        if (it != setik.begin() && *std::prev(it) >= mx) {
            smin(ans, abs(*prev(it) - a[i].second));
        }

        smax(mx, a[i].first);
    }

    printf("%d\n", ans);
}

int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        run();
    }
    return 0;
}

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

К примеру:

Для альбома $$$[\textbf{1}, \textbf{4}, 4, 3, \textbf{6}, 5, 6]$$$ сжатым будет альбом $$$[1, 4, 6]$$$.

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

Введём $$$dp_c$$$ — максимум впечатления, которое можно получить, если бы не было альбомов, таких, что в них есть элементы большие, чем $$$c$$$. Тогда, $$$dp_c$$$ равно $$$dp_{c-1}$$$, либо можно добавить ещё элемент или два, если в $$$c$$$ является максимальным элементом для какого-то альбом. Тогда для всех сжатых альбомов, можно пересчитаться через значение $$$dp$$$ в точке перед первым элементом альбома, либо через $$$c - 1$$$. Таким образом для пересчёта достаточно знать для каждого $$$c$$$ какие альбомы закончились в этом индексе, а так же для каждого альбома его первый элемент. Решение за $$$O(K)$$$

Давайте теперь решим полную задачу. Для каждого значения $$$c$$$ запомним индексы альбомов, которые содержат элемент равный $$$c$$$. Идём в порядке увеличения $$$c$$$, поддерживаем для каждого альбома значение $$$dp_i$$$ — максимум впечатления, который можно получить если бы не было элементов больших $$$c$$$ и Маша послушала последним $$$i$$$-й альбом. Пусть для очередного $$$c$$$ существует альбом $$$i$$$, что в нём есть песня с крутостью $$$c$$$. Тогда $$$dp_i$$$ надо взять максимумом из $$$dp_i + 1$$$ и значения по всем $$$dp_j + 1$$$, таких, что максимальный элемент в $$$j$$$-м альбоме меньше чем максимальный элемент $$$i$$$-го, так как она могла послушать этот трек, либо следующим в этом альбоме, либо после того, как послушала какой-то другой альбом полностью. Заметим, что можно хранить значение $$$mx$$$ — максимум по всем альбомам, для которых максимальное значение в них меньше $$$c$$$ и пересчитывать его при переходе к $$$c + 1$$$, храня те альбомы, которые закончились, тогда получится решение за $$$O(K + C)$$$.

#include "bits/stdc++.h"
#include <algorithm>
#include <locale>
#include <random>
#include <unordered_map>
#include <vector>

using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef long long ll;
typedef long double db;
typedef unsigned long long ull;

vector<int> shrink(vector<int> &a) {
  vector<int> a1;
  int n = a.size();
  int mx = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] > mx) {
      a1.emplace_back(a[i]);
      mx = a[i];
    }
  }
  return a1;
}

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> a(n);
  int k;
  for (int i = 0; i < n; ++i) {
    int k;
    cin >> k;
    a[i].resize(k);
    for (auto &j : a[i]) {
      cin >> j;
    }
  }
  vector<vector<int>> a1(n);
  for (int i = 0; i < n; ++i) {
    a1[i] = shrink(a[i]);
  }
  map<int, vector<int>> b;
  for (int i = 0; i < n; ++i) {
    for (auto &j : a1[i]) {
      b[j].emplace_back(i);
    }
  }
  vector<int> dp(n);
  int closed = 0;
  for (auto &it : b) {
    int c = it.first;
    int newclosed = 0;
    for (auto &i : it.second) {
      if (c == a1[i].back()) {
        dp[i] = max(dp[i] + 1, closed + 1);
        newclosed = max(newclosed, dp[i]);
        continue;
      }
      if (c == a1[i].front()) {
        dp[i] = closed + 1;
        continue;
      }
      dp[i] = max(dp[i] + 1, closed + 1);
    }
    closed = max(closed, newclosed);
  }
  cout << *max_element(all(dp));
}

signed main() {
  int t = 0;
  cin >> t;
  while (t --> 0) {
      solve();
      cout << '\n';
  }
  return 0;
}

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

Для общего случая можно написать $$$dp[v][best] = (\textit{min show}, \textit{max money})$$$, где $$$v$$$ — номер вершины где мы находимся, а $$$best$$$ — вершина с макс. $$$w_i$$$, через которую мы уже прошли. Можно показать, что оптимально сначала минимизировать количество шоу, а потом максимизировать количество денег. Эту динамику можно пересчитывать с помощью алгоритма Дейкстры. Асимптотика $$$O(mn \log n)$$$

#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define ar array
#define vec vector

using namespace std;

using ll = long long;
using pi = pair<int, int>;

using vi = vector<int>;
using vpi = vector<pair<int, int>>;

const ll INF = 2e18;
const int maxN = 3e5 + 10;

struct PathParams {
    ll num_show;
    int money;
};

bool operator==(const PathParams &a, const PathParams &b) {
    return tie(a.num_show, a.money) == tie(b.num_show, b.money);
}

bool operator!=(const PathParams &a, const PathParams &b) {
    return !(a == b);
}

struct State {
    PathParams params;
    int v;
    int best;
};

bool operator<(const PathParams &a, const PathParams &b) {
    if (a.num_show != b.num_show) return a.num_show < b.num_show;
    return a.money > b.money;
}

bool operator<(const State &a, const State &b) {
    return tie(a.params, a.v, a.best) < tie(b.params, b.v, b.best);
}

bool operator>(const State &a, const State &b) {
    return !(a < b);
}

void solve() {
    int n, m, p, group;
    cin >> n >> m >> p;
    vector dp(n, vector<PathParams>(n, {INF, 0}));
    vector<vpi> g(n);
    vi w(n);
    rep(i, n) cin >> w[i];
    rep(i, m) {
        int a, b, s;
        cin >> a >> b >> s;
        a--;
        b--;
        g[a].emplace_back(b, s);
    }
    dp[0][0] = {0, p};
    priority_queue<State, vector<State>, greater<>> pq;
    pq.push({.params = {.num_show=0, .money=p}, .v = 0, .best=0});
    while (!pq.empty()) {
        auto current = pq.top();
        pq.pop();
        int v = current.v;
        int best = current.best;
        if (dp[v][best] != current.params) continue;
        for (auto &[u, s]: g[v]) {
            auto state2 = current;
            PathParams &path = state2.params;
            if (path.money < s) {
                ll need = (s - path.money + w[best] - 1) / w[best];
                path.num_show += need;
                path.money += need * w[best];
                assert(path.money < s + w[best]);
            }
            path.money -= s;
            state2.v = u;
            if (w[u] > w[state2.best]) state2.best = u;
            if (path < dp[u][state2.best]) {
                dp[u][state2.best] = path;
                pq.push(state2);
            }
        }
    }
    ll ans = INF;
    rep(i, n) {
        ans = min(ans, dp[n - 1][i].num_show);
    }
    cout << (ans == INF ? -1 : ans) << '\n';
}

signed main() {
    int t = 1;
    cin >> t;
    rep(_, t) {
        solve();
    }
    return 0;
}

Для начала поймём, что от нас требуется. Дано дерево, в каждой вершине которого записан диапазон цен для этой вершины. Запрос это пара путей равной длины, цены на $$$i$$$-ых вершинах вдоль этих путей должны быть равны для всех $$$i$$$. Нужно найти количество способов расставить цены на вершинах для каждого префикса ограничений

Начнём с медленного решения задачи. Будем хранить компоненты связности(в каждой цены на вершинах должны быть равны). Для каждой из них храним допустимый диапазон цен. Ответом будет произведение длин диапазонов по всем компонентам. Будем идти вдоль путей и объединять 2 вершины в одну компоненту с помощью СНМ. Понятно, что для ускорения этого решения надо быстрее искать моменты, когда две вершины объединяются в одну компоненту.

Сначала разберём долгое решение. Сделаем heavy-light decomposition, с помощью которого будем хешировать пути в дереве, приняв за символ для вершины номер корня её компоненты. Теперь с помощью бинпоиска будем искать первый момент, когда хеши на префиксах путей различаются, то есть две вершины объединяются в одну компоненту. С помощью переливаний обновим для вершин корни их компонент и дерево отрезков для hld. Получим $$$n$$$ объединений, каждое найдём за $$$O(log^2(n))$$$ с помощью hld. Также будет $$$O(n \cdot log(n))$$$ обновлений в дереве отрезков из-за переливаний. На каждый запрос будет $$$O(log^2(n))$$$ от hld. Итоговая асимптотика $$$O((n + q) \cdot log^2(n))$$$

Теперь приведём красивое решение данной задачи. Начнём с бамбука.

Заменим равенство цен на паре путей на две пары путей с длинами равными максимальной степени двойки, меньшей длины исходного пути (как в sparse table). Теперь длины путей всех ограничений стали степеням двойки. Будем перебирать степени двойки в порядке убывания $$$2^k$$$, для каждого пути длины $$$2^k$$$ заведём вершину в графе, также заведём вершину для каждого такого пути в обратном порядке. Теперь ограничения задают рёбра в таком графе. Проведём их, выделим остовное дерево. Для каждого ребра из остова разделим ограничения на 2 ограничения с длинами путей в два раза меньше и продолжим процесс. На слое с длинами 1 получим нужное нам остовное дерево, которое будет отвечать за первые моменты, когда некоторые пары вершин объединялись в компоненты. Заметим, что с каждого слоя добавится вниз не более $$$2n$$$ рёбер, а также от запросов не более $$$2q$$$ рёбер. То есть каждый слой отработает за $$$O((n + q) \cdot \alpha(n))$$$, где $$$\alpha(n)$$$ — среднее время работы в снм, обратная функция Аккермана. Получили решение за $$$O((n + q) \cdot \alpha(n) \cdot log(n))$$$

Для полного решения на дереве для начала разобьём пару путей на три пары соответствующих вертикальных путей(возьмём из 4 конечных вершин этих путей самую близкую к lca пары вершин на её пути, тогда в пару к этому пути поставим вертикальный путь(часть другого пути), теперь получим один вертикальный путь и произвольный путь в дереве, разобьём второй путь по lca и первый по соответствующим длинам). Далее поступим аналогично бамбуку, только место вершины, отвечающей за отрезок, заведём вершину отвечающую за бинарный подъём в дереве на высоту равную степени двойки.

#include "bits/stdc++.h"

using namespace std;

const int mod = (int) 1e9 + 7;

int inv(int x) {
    int res = 1, n = mod - 2;
    while (n) {
        if (n & 1) {
            res = res * 1ll * x % mod;
        }
        x = x * 1ll * x % mod;
        n /= 2;
    }
    return res;
}

const int N = (int) 2e5 + 22, K = 18;
vector<int> g[N];
pair<int, int> a[N];
int n, q, ans = 1;
int h[N], up[N][K], lg[N];
vector<array<int, 3>> graph[K]; // lower vertex1, lower vertex2, time, vertex with direction
vector<array<int, 3>> gr[N];
vector<array<int, 3>> edges;

struct dsu {
    vector<int> p, sz;

    void build(int n) {
        p.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            sz[i] = 1;
        }
    }

    int get(int v) {
        return (v == p[v] ? v : p[v] = get(p[v]));
    }

    bool merge(int v, int u) {
        v = get(v), u = get(u);
        if (v != u) {
            if (sz[v] > sz[u]) {
                swap(v, u);
            }
            p[v] = u;
            sz[u] += sz[v];
            return true;
        }
        return false;
    }
} G, dsu[K];

void dfs(int v, int pr, int d) {
    h[v] = d;
    up[v][0] = pr;
    for (int j = 1; j < K; j++) {
        up[v][j] = up[up[v][j - 1]][j - 1];
    }
    for (auto u : g[v]) {
        dfs(u, v, d + 1);
    }
}

int la(int v, int x) {
    for (int j = 0; j < K; j++) {
        if (x >> j & 1) {
            v = up[v][j];
        }
    }
    return v;
}

int lca(int v, int u) {
    if (h[v] > h[u]) {
        swap(v, u);
    }
    u = la(u, h[u] - h[v]);
    if (v == u) {
        return v;
    }
    for (int j = K - 1; j >= 0; j--) {
        if (up[v][j] != up[u][j]) {
            v = up[v][j], u = up[u][j];
        }
    }
    return up[v][0];
}

int id(int v) {
    return (v > 0 ? v : -v + n);
}

int sgn(int v) {
    return (v > 0 ? 1 : -1);
}

void add_edge(int j, int v, int u, int t) {
    if (dsu[j].merge(id(v), id(u))) {
        if (j > 0) {
            if (sgn(v) == sgn(u)) {
                add_edge(j - 1, v, u, t);
                add_edge(j - 1, sgn(v) * up[abs(v)][j - 1], sgn(u) * up[abs(u)][j - 1], t);
            } else {
                if (sgn(v) == -1) {
                    swap(v, u);
                }
                add_edge(j - 1, v, sgn(u) * up[abs(u)][j - 1], t);
                add_edge(j - 1, sgn(v) * up[abs(v)][j - 1], u, t);
            }
        } else {
            edges.push_back({abs(v), abs(u), t});
        }
    }
}

void add(int v, int u, int x, int y, int t, int type1, int type2) {
    if (h[v] < h[u]) {
        swap(v, u);
    }
    if (h[x] < h[y]) {
        swap(x, y);
    }
    assert(h[v] - h[u] == h[x] - h[y]);
    int g = lg[h[v] - h[u]];
    if (type1 == type2) {
        add_edge(g, type1 * v, type2 * x, t);
        add_edge(g, type1 * la(v, h[v] - h[u] - (1 << g) + 1), type2 * la(x, h[x] - h[y] - (1 << g) + 1), t);
    } else {
        add_edge(g, type1 * v, type2 * la(x, h[x] - h[y] - (1 << g) + 1), t);
        add_edge(g, type1 * la(v, h[v] - h[u] - (1 << g) + 1), type2 * x, t);
    }
}

void merge(int v, int u) {
    v = G.get(v), u = G.get(u);
    if (v != u) {
        G.merge(v, u);
        if (G.sz[v] > G.sz[u]) {
            swap(v, u);
        }
        if (a[v].first <= a[v].second) {
            ans = ans * 1ll * inv(a[v].second - a[v].first + 1) % mod;
        }
        if (a[u].first <= a[u].second) {
            ans = ans * 1ll * inv(a[u].second - a[u].first + 1) % mod;
        }
        a[u].first = max(a[u].first, a[v].first);
        a[u].second = min(a[u].second, a[v].second);
        if (a[u].first > a[u].second) {
            ans = 0;
        } else {
            ans = ans * 1ll * (a[u].second - a[u].first + 1) % mod;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int j = 2; j < N; j++) {
        lg[j] = lg[j / 2] + 1;
    }
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int v;
        cin >> v;
        g[v].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        ans = ans * 1ll * (a[i].second - a[i].first + 1) % mod;
    }
    dfs(1, 1, 0);
    cin >> q;
    for (int j = 0; j < K; j++) {
        dsu[j].build(2 * n + 1);
    }
    for (int i = 0; i < q; i++) {
        int v, u, x, y;
        cin >> v >> u >> x >> y;
        int w = lca(v, u);
        int z = lca(x, y);
        if (h[v] - h[w] > h[x] - h[z]) {
            swap(v, x);
            swap(u, y);
            swap(w, z);
        }
        if (v != w) {
            int d = h[v] - h[w];
            int v2 = la(v, d - 1);
            int x2 = la(x, d - 1);
            add(v, v2, x, x2, i, 1, 1);
            v = up[v2][0];
            x = up[x2][0];
        }
        if (x != z) {
            int d = h[x] - h[z];
            int v2 = la(u, (h[u] - h[v]) - d);
            int x2 = la(x, d - 1);
            add(v, up[v2][0], x, x2, i, -1, 1);
            v = v2;
            x = up[x2][0];
        }
        add(v, u, x, y, i, (h[v] > h[u] ? 1 : -1), (h[x] > h[y] ? 1 : -1));
    }
    G.build(n + 1);
    int j = 0;
    for (int i = 0; i < q; i++) {
        while (j < (int) edges.size() && edges[j][2] == i) {
            merge(edges[j][0], edges[j][1]);
            j++;
        }
        cout << ans << '\n';
    }
}

За $$$A$$$ обозначим максимальное значение $$$a_i$$$

Для начала решим задачу за $$$O(n \cdot k \cdot f(k, A))$$$ с помощью динамического программирования.

Положим $$$dp[i][j]$$$ — максимальный возможный объем наименьшего кусочка, если по первым $$$i$$$ измерениям мы разделили шоколадку на $$$j$$$ частей. Если мы разделили более чем на $$$k$$$ частей, так же положим результат в $$$dp[i][k]$$$. В пересчете нам нужно решить на сколько часей делить шоколадку вдоль очередного измерения. Рассмотрим несколько способов это сделать.

• Можно за $$$O(k)$$$ перебрать состояние, в которое переходим, и из этого посчитать на сколько частей нужно разделить шоколадку вдоль очередного измерения. — Получим $$$O(n \cdot k^2)$$$

• Можно за $$$O(A)$$$ перебрать на сколько частей мы делим шоколадку вдоль очередного измерения.

• Находясь в состоянии $$$dp[i][j]$$$, можно перебирать $$$b_i$$$ — на сколько частей делить шоколадку, пока $$$j \cdot b_i \le k$$$. Можно показать, что такое решение будет работать за $$$O(n \cdot k \cdot \ln{k})$$$

Ключевая идея

• предположим нам нужно разделить шоколадку на $$$10$$$ частей, и вдоль первых измерений мы уже разделили её на $$$5$$$ частей, или на $$$6$$$ частей, или на $$$7, 8$$$ или $$$9$$$ частей. Все эти состояния не различимы для нас, потому что во всех этих случаях нам нужно разделить шоколадку ещё хотя бы на $$$2$$$ части. Осталось понять сколько всего таких <<интересных>> состояний и научиться их хранить. Для этого есть несколько подходов, разберем один из них:

• нам интересны все значения $$$\lceil \frac{k}{i} \rceil$$$ для $$$i = 1, 2, \ldots k$$$ — это то, на сколько частей ещё может быть нужно разделить шоколадку. Среди них всего $$$O(\sqrt{k})$$$ различных, так как либо $$$i \le \sqrt{k}$$$, либо само значение $$$\lceil \frac{k}{i} \rceil \le \sqrt{k}$$$. Если сделать все эти числа состояниями, и пересчитываться, перебирая состояние, в которое переходить, получим $$$O(n \cdot \sqrt{k} \cdot \sqrt{k}) = O(n \cdot k)$$$ — этого всё ещё не достаточно, чтобы решить полую задачу.

Последнее наблюдение

Если мы находимся в состоянии $$$dp[i][remain]$$$ где $$$remain = \lceil \frac{k}{i} \rceil$$$ для какого-то $$$i$$$ — применим к нему ту же идею. Из него нам интересны переходы в состояния $$$\lceil \frac{remain}{j} \rceil$$$ для $$$j = 1, 2, \ldots remain$$$. Какая асимптотика получится, если перебирать только интересные переходы?

$$$n \cdot (\sum\limits_{r=1}^{\sqrt{k}}{ 2 \cdot \sqrt{r} + 2 \cdot \sqrt{\lceil \frac{k}{r} \rceil}})$$$

• можно показать, что это $$$O(n \cdot k^{3/4})$$$ — что решает задачу

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

const int MAXN = 200;
int a[MAXN];

const int MAXK = 1e7 + 100, MAXH = 1e4;
int hsh[MAXK];
int rev[MAXH];

double dp[MAXN][MAXH];

vector<array<int, 2>> go[MAXH];

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int id = 0;
    for (int c = 1;; ++id) {
        rev[id] = (k + c - 1) / c;
        hsh[(k + c - 1) / c] = id;
        int t = (k + c - 1) / c - 1;
        if (t == 0) break;
        c = (k + t - 1) / t;
    }
    ++id;
    dp[0][hsh[k]] = k;

    for (int i = 0; i < id; ++i) {
        int k = rev[i];
        for (int c = 1;;) {
            go[i].push_back({c, hsh[(k + c - 1) / c]});
            int t = (k + c - 1) / c - 1;
            if (t == 0) break;
            c = (k + t - 1) / t;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < id; ++j) {
            double val = dp[i][j];
            if (val == 0) continue;
            for (auto elem : go[j]) {
                int c = elem[0], k1 = elem[1];
                if (c > a[i]) break;
                int cur = a[i] / c;
                dp[i + 1][k1] = max(dp[i + 1][k1], val * cur / a[i]);
            }
        }
    }
    cout << fixed << setprecision(20);
    cout << dp[n][hsh[1]] << '\n';
    return 0;
}

Воспользуемся структурой Ахо-Корасик для хранения строк из $$$S$$$. Построим на нём сжатые суффиксные ссылки. Так можно чуть оптимальнее найти все строки из $$$S$$$, заканчивающиеся в данной позиции $$$t$$$.

Обозначим за $$$pref[i]$$$ число подстрок из $$$S$$$ у префикса $$$t$$$ длины $$$i$$$.

Обозначим за $$$suf[i]$$$ число подстрок из $$$S$$$ у суффикса $$$t$$$ начиная с позиции $$$i$$$.

Заметим, что $$$pref[r] + suf[l] - pref[|t|]$$$ равно числу подстрок строки $$$t$$$ из $$$S$$$ на отрезке $$$[l, r]$$$ минус число подстрок $$$t$$$ из $$$S$$$, которые начинаются раньше $$$l$$$ и заканчиваются позже $$$r$$$.

Для каждого запроса найдём подстроку $$$t$$$, совпадающую с $$$s_i$$$, которая покрывает строку $$$t[l, r]$$$ и заканчивается как можно ближе к $$$r$$$. Если такой нет, то ответ можно посчитать по предыдущей формуле. Иначе $$$t[l, r]$$$ вкладывается в $$$s_i[l', r']$$$. При этом в строке $$$s_i$$$ нет подстрок из $$$S$$$, начинающихся раньше $$$l'$$$ и заканчивающихся позже $$$r'$$$. Для получения ответа применим прошлую формулу строкой $$$s_i$$$ и подотрезком $$$[l', r']$$$.

Асимптотика: $$$O(S + |t| + m \log m)$$$

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

struct node {
	int nx[26];
	int p;
	int pp;
	int len;
	int id;
	int cnt;
	bool term;

	node() : p(-1), pp(-1), len(0), id(-1), term(false), cnt(0) {
		for (int i = 0; i < 26; i++) {
			nx[i] = -1;
		}
	}
};

vector<node> g;

vector<string> s[2];

string t[2];

vector<vector<long long>> c[2], pid[2];

vector<long long> tc[2];

int add(int a, char c) {
	c -= 'a';
	if (g[a].nx[c] == -1) {
		g[a].nx[c] = g.size();
		g.emplace_back();
		g.back().len = g[a].len + 1;
	}
	return g[a].nx[c];
}

void build_aho(int a) {
	vector<pair<int, int>> q;
	for (int i = 0; i < 26; i++) {
		if (g[a].nx[i] == -1) {
			g[a].nx[i] = a;
		} else {
			q.emplace_back(a, i);
		}
	}

	int qb = 0;
	while (qb < q.size()) {
		int b = q[qb].x;
		int i = q[qb].y;
		qb++;
		int v = g[b].nx[i];
		int c = g[b].p;

		if (g[v].term) {
			g[v].cnt = 1;
		}

		if (c == -1) {
			g[v].p = a;
			g[b].pp = -1;
		} else {
			g[v].p = g[c].nx[i];
			if (g[v].term) {
				g[v].pp = v;
			} else {
				g[v].pp = g[g[v].p].pp;
			}
			g[v].cnt += g[g[v].p].cnt;
		}

		for (int i = 0; i < 26; i++) {
			if (g[v].nx[i] == -1) {
				g[v].nx[i] = g[g[v].p].nx[i];
			} else {
				q.emplace_back(v, i);
			}
		}
	}
}

vector<vector<pair<int, int>>> ts;
vector<int> qlen;
priority_queue<pair<int, int>> h;
vector<long long> ans;

long long get_ans(int rdst, int len, vector<long long>& a, vector<long long>& b, bool substr) {
	int l = a.size() - 1 - rdst;
	int r = l + len;
	long long cnt = a[r] + b[a.size() - 1 - l] - a.back();
	if (substr && l == 0 && r == a.size() - 1) {
		cnt++;
	}

	return cnt;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;
	g.emplace_back(); g.emplace_back();
	s[0].resize(n); s[1].resize(n);
	c[0].resize(n); c[1].resize(n);
	pid[0].resize(n); pid[1].resize(n);
	ans.resize(m);

	cin >> t[0];
	t[1] = t[0];
	reverse(t[1].begin(), t[1].end());
	ts.resize(t[0].size());

	for (int i = 0; i < n; i++) {
		cin >> s[0][i];
	}
	sort(s[0].begin(), s[0].end(), \ 
	[](const string& a, const string& b) { return a.size() < b.size(); });

	for (int i = 0; i < n; i++) {
		s[1][i] = s[0][i];
		reverse(s[1][i].begin(), s[1][i].end());

		for (int e = 0; e < 2; e++) {
			int a = e;
			for (auto j : s[e][i]) {
				a = add(a, j);
			}
			g[a].term = true;
			g[a].id = i;
		}
	}

	build_aho(0); build_aho(1);

	for (int e = 0; e < 2; e++) {
		tc[e].resize(t[0].size() + 1);

		int a = e;
		for (int i = 0; i < t[0].size(); i++) {
			a = g[a].nx[t[e][i] - 'a'];
			tc[e][i + 1] = tc[e][i] + g[a].cnt;
		}
		for (int i = 0; i < n; i++) {;
			c[e][i].resize(s[0][i].size() + 1);
			pid[e][i].resize(s[0][i].size() + 1, -1);

			int a = e;
			for (int j = 0; j < s[e][i].size(); j++) {
				a = g[a].nx[s[e][i][j] - 'a'];
				c[e][i][j + 1] = c[e][i][j] + g[a].cnt;
				
				if (g[a].term) {
					pid[e][i][j + 1] = g[a].id;
				}
			}

			for (int j = (int)s[e][i].size() - 1; j >= 0; j--) {
				if (pid[e][i][j] == -1) {
					pid[e][i][j] = pid[e][i][j + 1];
				}
			}
			c[e][i].back()--;
			
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		ts[b - 1].emplace_back(a, i);
		qlen.emplace_back(b - a);
	}

	int a = 0;
	for (int i = 0; i < t[0].size(); i++) {
		for (auto j : ts[i]) {
			h.emplace(j);
		}

		a = g[a].nx[t[0][i] - 'a'];

		if (g[a].pp != -1) {
			int id = g[g[a].pp].id;
			int bg = i + 1 - (int)s[0][id].size();
			while (h.size() > 0 && h.top().x >= bg) {
				int rdst = i - h.top().x + 1;
				int nid = pid[1][id][rdst];


				ans[h.top().y] = get_ans(rdst, qlen[h.top().y], 
				    c[0][nid], c[1][nid], true);
				h.pop();
			}
		}
	}

	while (h.size() > 0) {
		ans[h.top().y] = get_ans(t[0].size() - h.top().x, qlen[h.top().y], tc[0], tc[1], false);
		h.pop();
	}

	for (auto i : ans) {
		cout << i << ' ';
	}
	cout << '\n';
}