Перестановка∗ p длины n записана по часовой стр...

Идея решения — Segment Tree + Lazy Propagation

Решим задачу за $O(n\log n)$ на один тест.

Главная идея: будем рассматривать все возможные начальные позиции одновременно и поддерживать количество блоков для каждой из них.

1. Как изменяется количество блоков?

Пусть у нас есть множество $S$, и мы добавляем в него новое число $x$.

Возможны четыре ситуации:

Таким образом,

Здесь квадратные скобки равны 1, если условие истинно, и 0 иначе.

Это ключевое наблюдение: при добавлении одного числа количество блоков изменяется только на $-1$, $0$ или $+1$.

2. Рассмотрим перестановку как удвоенный массив

Чтобы удобно работать с циклическими сдвигами, мысленно допишем перестановку к самой себе:

Каждая начальная позиция $s$ соответствует подмассиву длины $n$:

Будем двигать правую границу $r$ слева направо.

Для каждой начальной позиции $s$ хотим поддерживать количество блоков в множестве

Если в какой-то момент число блоков стало хотя бы 3, позиция $s$ навсегда становится плохой.

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

3. Как обновлять сразу много начальных позиций?

Пусть сейчас добавляем $x=a_r$.

Будем хранить last[v] — последнюю позицию числа $v$ перед текущей позицией $r$.

Для начальной позиции $s$ число $x-1$ уже находится в рассматриваемом подмассиве тогда и только тогда, когда

Аналогично для $x+1$.

Поэтому изменение количества блоков можно выполнить тремя операциями:

1. Прибавить $1$ всем началам $s\le r$.
2. Вычесть $1$ для всех $s\le last[x-1]$, если $x>1$.
3. Вычесть $1$ для всех $s\le last[x+1]$, если $x<n$.

Все эти операции — прибавление числа на отрезке, что удобно делать деревом отрезков с lazy propagation.

В дереве будем хранить максимальное количество блоков среди рассматриваемых начал.

Если для некоторого начала количество блоков достигло 3, найдём такую позицию и исключим её навсегда, установив значение $-INF$.

Каждая позиция исключается не более одного раза.

Решение на C++17

cpp

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

const int NEG = -1000000000;

struct SegTree {
    int n;
    vector<int> mx, lazy;

    SegTree(int n) : n(n) {
        mx.assign(4 * n + 5, 0);
        lazy.assign(4 * n + 5, 0);
    }

    void apply(int v, int val) {
        mx[v] += val;
        lazy[v] += val;
    }

    void push(int v) {
        if (lazy[v] != 0) {
            apply(v * 2, lazy[v]);
            apply(v * 2 + 1, lazy[v]);
            lazy[v] = 0;
        }
    }

    void pull(int v) {
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    }

    void add(int v, int tl, int tr,
             int l, int r, int val) {
        if (l > r) return;

        if (l == tl && r == tr) {
            apply(v, val);
            return;
        }

        push(v);
        int tm = (tl + tr) / 2;

        add(v * 2, tl, tm,
            l, min(r, tm), val);

        add(v * 2 + 1, tm + 1, tr,
            max(l, tm + 1), r, val);

        pull(v);
    }

    void add(int l, int r, int val) {
        if (l <= r)
            add(1, 1, n, l, r, val);
    }

    // Найти позицию со значением >= 3
    // внутри отрезка [l, r].
    int find_bad(int v, int tl, int tr,
                 int l, int r) {
        if (l > r || mx[v] < 3)
            return -1;

        if (tl == tr)
            return tl;

        push(v);
        int tm = (tl + tr) / 2;

        int res = find_bad(
            v * 2, tl, tm,
            l, min(r, tm)
        );

        if (res == -1) {
            res = find_bad(
                v * 2 + 1, tm + 1, tr,
                max(l, tm + 1), r
            );
        }

        return res;
    }

    int find_bad(int l, int r) {
        if (l > r) return -1;
        return find_bad(1, 1, n, l, r);
    }

    void erase(int v, int tl, int tr, int pos) {
        if (tl == tr) {
            mx[v] = NEG;
            lazy[v] = 0;
            return;
        }

        push(v);
        int tm = (tl + tr) / 2;

        if (pos <= tm)
            erase(v * 2, tl, tm, pos);
        else
            erase(v * 2 + 1, tm + 1, tr, pos);

        pull(v);
    }

    void erase(int pos) {
        erase(1, 1, n, pos);
    }
};

void solve() {
    int n;
    cin >> n;

    vector<int> p(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> p[i];

    SegTree st(n);

    vector<int> last(n + 2, 0);

    int ans = n;

    for (int r = 1; r <= 2 * n - 1; r++) {
        int x = p[(r - 1) % n + 1];

        int R = min(r, n);

        // Добавляем новый элемент x
        st.add(1, R, 1);

        // Если x-1 уже присутствует,
        // новый блок не создаётся
        if (x > 1) {
            st.add(1, min(last[x - 1], n), -1);
        }

        // Если x+1 уже присутствует,
        // блоки могут объединиться
        if (x < n) {
            st.add(1, min(last[x + 1], n), -1);
        }

        last[x] = r;

        // Только подмассивы длины <= n
        int L = max(1, r - n + 1);

        // Удаляем все плохие начала
        while (true) {
            int pos = st.find_bad(L, R);

            if (pos == -1)
                break;

            st.erase(pos);
            ans--;
        }
    }

    cout << ans << '\n';
}

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

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Пример работы

Рассмотрим перестановку:

Для начальной позиции $s=1$ получаем:

Добавление элементов Шаг из 5

Количество блоков

[Назад] [Далее]

После добавления числа $5$ имеем: