Lelyte

Корневые оптимизации

2022-09-16T16:20:10.703Z

Корневая декомпозиция

Рассмотрим такую задачу
Мы хотим делать две операции:
1) a[l; r] += x
2) a[l; r] < x

Решение:
Разобьем наш массив на K блоков (спойлер. K = √n)
Тогда наш отрезок запроса разобьется на неполные блоки (по краям), а так же на полные блоки

Для каждого неполного блока сделаем операции в тупую за O(√n)

Теперь рассмотрим полные блок

Для операции 1:
Будем хранить в массиве buff[i] (где i - номер блока) - сколько мы добавили в блок i

Для операции 2:

Будем хранить отсортированные отрезки. Отвечать будем на запросы с помощью Бинарного поиска за O(LogN) для блока. То есть возьмем числа, для которых верно: a[i] + buff[num(i)] < x

Алгоритм МО

Рассмотрим такую задачу
Дано много-много запросов, состоящий из границ отрезка и числа x
Вам нужно для каждого отрезка ответить на вопрос: Сколько чисел, лежащий в нашем отрезке равны x?

Решение:
Воспользуемся Алгоритмом МО

Для начала, чтобы все работало намного быстрее, чем сейчас - сожмем числа
То есть:
Пусть есть массив [1, 5, 3, 6, 1, 6] -> [1, 2, 3, 4, 1, 4]

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

Дальше, внутри каждого нового блока посчитаем ответ в тупую для первого отрезка

Дальше, для каждого блока будем двигать левые границы в тупую, а правую - только направо

Тогда суммарно наша правая граница пройдет максимум N элементов => работает за O(N)

Всего блоков √n => Суммарная асимптотика O(n√n)

Военная хитрость:

Нечетные блоки отсортируем по возрастанию, четные - по убыванию (это будет работать быстрее)

лол

Оптимизация какого-то что?

жесть там какие-то тяжелые и легкие вершины, но задача изи короче мне пофиг

Z-функция, Префикс-Функция, Бор, Манакер

2022-06-13T08:52:27.968Z

Z-функция

Z-функция - это длина максимального префикса подстроки S, который начинается в x, который одновременно является префиксом нашей строки S
s[x ... x + k] == s[0 ... k]

Код:

int n;
str s;
vector<int> z(n);
int l = 0, r = 0;
for(int i = 1; i < n; i++){
    if(i <= r){
        z[i] = min(z[i - l], r - i + 1);
    }
    while(z[i] + i < n && s[z[i]] == s[z[i] + i]){
         z[i]++;
    }
    if(z[i] + i - 1 > r){
        l = i;
        r = z[i] + i - 1;
    }
}

Префикс Функция

Префикс функцией от строки S называется такой массив p, где Pi - это длина наибольшего префикса длинны S, который также является суффиксом i-того префикса (не считая весь i-й префикс)

Например, для строки "aataataa" префикс функция будет равна [0,1,0,1,2,3,4,5]

Код:

int n;
str s;
vector<int> p(n);
for(int i = 1; i < n; i++){
    int tmp = p[i - 1]
    while(s[i] != s[tmp] && tmp){
        tmp = s[tmp - 1]
    }
    if(s[i] == s[tmp]){
        p[i] = tmp + 1;
    }
}

Манакер

Пусть у нас есть строка S и мы хотим в ней найти все подпалиндромы

https://ru.algorithmica.org/cs/string-searching/manacher/ - тут

Бор

Бор — это структура данных для компактного хранения строк

ДП по подмножествам, ДП по профилю

2022-06-11T07:46:53.377Z

ДП по подмножествам

Вопросы, на которые вы должны сами отвечать

Что считаем?
Как считаем?
В каком порядке считаем?
Какие начальные значения?
Где ответ?

Гамильтонов путь

dp[last][mask] = min длина Гамильтонова пути из S в Last, если посетить вершины mask
dp[last][mask] -> dp[next][mask | (1 << next)]
next не принадлежит mask
last->next есть в графе
𝒪(2^n * n^2)

Начальные значения:
dp[s][1 << s] = 0, остальные - INF

Где ответ?
dp[i][полная маска]

Кол-во гамильтоновых путей из вершины S

dp[last][mask] = кол-во Гамильтоновых путей из S в last, если посетили вершины mask
dp[last][mask] -> dp[next][mask | (1 << next)]
next не принадлежит mask
last->next есть в графе
dp[s][1 << s] = 1
dp[next][mask | (1 << next)] += dp[last][mask]

Ответ?
SUM dp[i][(1 << n) - 1]

Введите текст

Есть числа 0...2^n - 1
a[0], a[1], .. a[2^n - 1]
Для каждой mask посчитать сумму:
SUM a[i], где i - подмаска нашей маски

Пример:
mask = 6 = 100
a[000] + a[010] + a[100] + a[110]

int n;
for(int mask = 0; mask < (1 << n); mask++){
    for(int submask = mask; submask > 0; submask=(submask - 1)&mask){
        ...
    }
}

dp[mask][i] - сумма a[submask], где биты 0...I в mask и subtask могут различаться, а остальные совпадают

dp[mask][0] = a[mask]
Если i-тый бит mask = 0, то dp[mask][i + 1] = dp[mask][i]
Иначе dp[mask][i + 1] = dp[mask][i] + dp[mask ^ (1 << i)][i]

for(int i = 0; i < n; i++){
    for(int mask = 0; mask < (1 << n); mask++){
        dp[mask][i + 1] = dp[mask][i]
        if((mask >> i) & 1){
            dp[mask][i + 1] += dp[mask ^ (1 << i)][i]
        }
    }
}

Оптимизация: можно сделать dp - одномерным, тогда получим такой код:

for(int i = 0; i < n; i++){
    for(int mask = 0; mask < (1 << n); mask++){
        if((mask >> i) & 1){
            dp[mask] += dp[mask ^ (1 << i)]
        }
    }
}

Работает столько же, но памяти намного меньше

ДП по профилю

пошли нафиг

https://wiki.algocode.ru/index.php?title=ДП_по_профилю

Дерево Фенвика + Sparse Table ~ Сириус 07.06

2022-06-07T07:53:01.593Z

Дерево Фенвика

Дерево Фенвика - структура данных, дерево на одномерном массиве, которая обладает такими свойствами, как:

Сумма на отрезке с L по R
Изменение значения в какой-то позиции за O(LogN)
Требует O(N) памяти

Код:

ll n;
vector<ll> sum;

ll get_sum(ll i){ //сумма
    ll ans = 0;
    for(; i >= 0; i = (i&(i+1))-1){
        ans += sum[i];
    }
    return ans;
}

void update(ll i, ll x){ //обновление на точке
    for(; i < n; i = (i | (i+1))){
        sum[i] += x;
    }
}

ll sum_otr(ll l, ll r){
    return get_sum(r) - get_sum(l-1);
}

Так же можно сделать MAX на отрезке, но это извращение, проще написать ДО

Двумерное Дерево Фенвика

Аналогично

Код (скорее всего с багами):

ll n;
vector<vector<ll>> f(MAXN, vector<ll>(MAXN));


ll get_sum(int i, int j){
    int r = 0;
    while(j > 0){
        int k = i;
        while(k > 0){
            r += f[k][j];
            k -= k & -k;
        }
        j = j & -j;
    }
    return r;
}


ll sum(int x1, int y1, int x2, int y2){
    return get_sum(x2, y2) - get_sum(x1, y2) - get_sum(x2, y1) + get_sum(x1, y1);
}

void add(int i, int j, int x){
    while(j <= n){
        int k = i;
        while(k <= n){
            f[k][j] += x;
            k += k & (~k);
        }
        j += j & (~j);
    }
}

Sparse Table

Sparse Table - структура данных, позволяющая находить минимум на отрезке

#define MAX 100010
#define LOGMAX 30

ll n;
vector <ll> arr;
vector <vector<ll>> Sparce(MAX, vector<ll>(LOGMAX));

ll task(ll l, ll r) {
    ll j = (ll) log2(r - l + 1);
    if (Sparce[l][j] <= Sparce[r - (1 << j) + 1][j]) {
        return Sparce[l][j];
    }
    return Sparce[r - (1 << j) + 1][j];
}

...
в функции main 
for (ll i = 0; i < n; i++) {
    Sparce[i][0] = arr[i];
}
for (ll j = 1; (1 << j) <= n; j++) {
    for (ll i = 0; (i + (1 << j) - 1) < n; i++) {
        if (Sparce[i][j - 1] < Sparce[i + (1 << (j - 1))][j - 1]) {
            Sparce[i][j] = Sparce[i][j - 1];
        } else {
            Sparce[i][j] = Sparce[i + (1 << (j - 1))][j - 1];
        }
    }
}

Оптимизация:

#define MAX 100010
#define LOGMAX 30
ll n;
vector <ll> arr;
vector <vector<ll>> Sparce(LOGMAX, vector<ll>(MAX));

ll task(ll l, ll r) {
    ll j = (ll) log2(r - l);
    return min(Sparce[j][l], Sparce[j][r - (1 << j)]);
}


int main() {
    for (ll i = 0; i < n; i++) {
        Sparce[0][i] = arr[i];
    }
    for (ll j = 0; j < LOGMAX - 1; j++) {
        for (ll i = 0; i + (2 << j) <= n; i++) {
            Sparce[j + 1][i] = min(Sparce[j][i], Sparce[j][i + (1 << j)]);
        }
    }
}

Disjoint Sparse Table

Sparse Table не мог быть построен для тех функций от подотрезка массива, для которых каждое число подотрезка должно быть учтено ровно один раз. Disjoint Sparse Table решает эту проблему и с предподсчётом за O(nlogn) позволяет в онлайне за O(1) находить почти любые функции от подотрезка, например кол-во минимумов, или произведение по непростому модулю. ~ wiki.algocode.ru

Основная идея: разделяй и властвуй

TODO: написать дальше, автор конспекта закрыл ноут и пошел внимательно слушать

Ссылки данной штуки: https://algorithmica.org/ru/sparse-table, https://wiki.algocode.ru/index.php?title=Disjoint_Sparse_Table

Теория Чисел ~ Сириус 05.06

2022-06-05T07:27:56.838Z

Основная теорема арифметики

Основная теорема арифметики гласит, что каждое число раскладывается на простые множители, причем единственным образом

Факторизация за O(sqrtN)

Пусть у нас есть число N
Оно представимо в виде N = a * b. Заметим, что одно из чисел a и b <= sqrt(n) (иначе a * b > n) => можно перебирать делители N до его корны

Решето Эратосфена за O(NLogLogN)

//БУДЬТЕ АККУРАТНЕЙ С ПЕРЕПОЛНЕНИЕМ!!!
int n;
vector<bool> isPrime(n);
for(int i = 2; i <= n; i++){
    isPrime[i] = true;
}
for(int i = 2; i * i <= n; i++){
    if(isPrime[i]){
        for(int j = i * i; j <= n; j++){
            isPrime[j] = false;
        }
    }
}

Прикол с minDiv (чтобы факторизацию делать)

int n;
vector<int> minDiv(n);
vector<bool> isPrime(n);
for(int i = 2; i <= n; i++){
    isPrime[i] = true;
    minDiv[i] = i;
}
for(int i = 2; i * i <= n; i++){
    if(isPrime[i]){
        for(int j = i * i; j <= n; j++){
            isPrime[j] = false;
            minDiv[j] = min(minDiv[j], i);
        }
    }
}

Диофантовы уравнения

Уравнения вида a*x + b*y = c (a, b, c - известны)

Прикол:
Если (a, b) = g, то существуют x и y такие, что a*x + b*y = g
(a, b) -> (b, a % b)
b * x1 + (a % b) * y1 = g
(Для тех, кто не знал - a % b = a - [a / b] * b)
b*x1 + (a - [a / b] * b) * y1 = a * y1 + b * (x1 - [a / b] * y1)
Пример шапки функции:

int gcd(int a, int b, int &x, int &y){
    ...
}

Заметим, что a * (x + b) + b (y - a) = a * x + b * y => x = x0 + t * b/g;
y = y0 - t * a/g

Теперь решим основную задачу
Воспользуемся тем, что мы умеем решать для НОДа и тупо домножим коэффициенты.
Если c % g == 0 => решений бесконечно много
Если c % g != 0 => решений нет

Функция Эйлера

ф(n) (да, это фи) - количество взаимнопростых чисел, которые меньше n
ф(10) = 4

Заметим тупые свойства:

ф(р) = р - 1
ф(р^n) = p^n - p^(n - 1)

Так же интересное свойство:
ф(a) * ф(b) = ф(a*b) для (a, b) = 1 (я не собираюсь это доказывать, так как а) это никому не нужно, б) это долго и скучно)

Тогда достаточно просто считается ф(n) для любого n
ф(n) = ф(p1^L1 * p2^L2 * p3^L3 * ... ) = ф(p1^L1) * ф(p2^L2) * ... = (тупое свойство 2) = n * (p1 - 1 / p1) * ... * (pK - 1 / pK)
(лучше считать через ans / p, ans *= (p - 1)

int n;
int ans = n;
for(int i = 2; i * i <= n; i++){
    if(n % i == 0){
        ans /= i;
        ans *= (i - 1);
        while(n % i == 0){
            n /= i;
        }
    }
}
if(n > 1){
    ans /= n;
    ans *= (n - 1);
}

Количество делителей числа

Пусть у нас n = p1^L1 + p2^L2 + p3^L3 + ... + pK^LK
Тогда, кол-во делителей = (L1 + 1) * (L2 + 2) * (L3 + 3) * ... * (LK + 1) (очевидно)

Малая Теорема Ферма

a^(p - 1) ≡ 1 (mod p) при (a, p) = 1

Теорема Эйлера

a^ф(n) ≡ 1 (mod m) при (a, m) = 1

Функции модульной арифметики

const int MOD = 998244353;


int add(int a, int b){
    if(a + b >= MOD){
        return a + b - MOD;
    }
    else{
        return a + b;
    }
}


int sub(int a, int b){
    if(a - b < 0){
        return a + b - MOD;
    }
    else{
        return a - b;
    }
}

Китайская теорема об остатках

TODO (сори, я не успел записать)

Мем с модулями

a * g ≡ b * g (mod m * g) -> a ≡ b (mod m)
a * g ≡ b * g (mod m) -> a ≡ b (mod m) при (m, g) = 1
a ≡ b (mod m) -> a + x ≡ b + x (mod m)

С из N по K

(n, k) = n! / (k! * (n - k)!)
n! = (n - 1)! * n

надеюсь я с комментариями нигде не напутал...

int n;
int f[n], rf[n];
for(int i = 1; i < n; i++){
    f[i] = mul(f[i - 1], i); //умножение чисел по модулю
}
rf[n - 1] = inv(f[n - 1]); //обратное число по модулю
for(int i = n - 2; i >= 0; i--){
    rf[i] = mul(rf[i + 1], i + 1); //умножение чисел по модулю
}

Мемы:
1/n = (n - 1)! / n!
N^-1 = f[N - 1] * rf[N] (mod M)

Задачка

Надо найти все простые числа на отрезке [L, R]
(R-L+1 < 1e7)

int l, r;
vector<int> primes; //предпосчитать
vector<bool> isPrime(r - l + 1, true);
for(auto &i : primes){
    for(int j = i * max((l + i - 1) / i, i); j <= r; j += i){
        isPrime[j - l] = false;
    }
}

Линейное решето Эратосфена

int n;
vector<int> minDiv(n);
vector<int> primes;
iota(minDiv.begin(), minDiv.end(), 0);
for(int i = 2; i < n; i++){
    if(minDiv[i] == i){
        primes.pb(i);
    }
    for(auto &p : primes){
        if(p > minDiv[i] || p * i >= n){
            break;
        }
        minDiv[p * i] = p;
    }
}

ScanLine ~ Сириус 04.06

2022-06-04T07:15:25.763Z

КОНСПЕКТ ЕЩЕ ПИШЕТСЯ!!!

Задача - Объединение прямоугольников

Задача заключается в том, что на плоскости имеется N прямоугольников,
стороны которых параллельны осям координат. Требуется вычислить площадь объединения данных прямоугольников

Тупняк - Сделаем буловую табличку, по размеру достаточную, чтобы туда поместились все наши прямоугольники. Перебираем все прямоугольники. Смотрим на очередной. Поставим в табличку единички в те клетки, которые лежат в каждом прямоугольнике. Это работает за 𝒪(𝑛𝑆), где 𝑆 — площадь таблички, так как мы 𝑛 раз проходим по табличке площади 𝑆.

Решение за 𝒪(𝑛 log 𝑛) - Здесь мы сжимаем координаты.
Теперь будем хранить одну вертикальную полоску длины, равной высоте таблицы. Хранить будем, как массив интов. Делаем сканалйн по 𝑥-ам. В этой полоске поддерживаем сколько из еще открытых прямоугольников имеют данную координату по 𝑥. Открылся новый прямоугольник — ко всем нужным 𝑦 в полоске прибавили единичку. Закрылся — вычитаем единичку. Чтобы найти площадь на текущем столбце, нужно сложить площади всех точек, в которых
записан не ноль. Получили сложность 𝒪(𝑛2). Можно оптимизировать с помощью ДО на 𝒪(𝑛 log 𝑛)

Так же ссылочка на решение челика на Codeforces - https://codeforces.com/blog/entry/49797

Задача - Найти точку, накрытой наибольшим количеством прямоугольников

Даны n прямоугольников. Надо найти точку, которая покрыта максимальным количеством прямоугольников.

Решение человека с Codeforces:

Давайте возьмем y-координаты всех точек, для которых нужно определить количество прямоугольников, покрывающих их, и отметим их на вертикальной прямой, находящейся в x = - ∞. Давайте теперь начнем непрерывно двигать эту прямую до x = + ∞ и поддерживать для каждой точки количество прямоугольников, покрывающих ее.

Собственно, вопрос: а в какие моменты данные количества будут изменяться? Ответ: когда наша прямая "входит" в прямоугольник (то есть, проходит через координату x = xleft и когда она "выходит" из него (проходит через координату x = xright). Ну, собственно говоря, мы можем построить отсортированный массив т.н. "событий", где события — это вход в прямоугольник, выход из прямоугольника и ответ на запрос количества покрывающих точку прямоугольников. Соответственно, для события входа в прямоугольник мы прибавляем единичку на отрезке [ybottom; ytop], для события выхода из прямоугольника — отнимаем единичку на соответствующем отрезке, а для события ответа на запрос — сохраняем значение количества покрывающих точку прямоугольников.

PS - https://codeforces.com/blog/entry/49588

Так же решение человека с форума emaxx (в конце написан код, но как говорит автор, он с багами, но баги в ДО) - https://e-maxx.ru/forum/viewtopic.php?id=368

Задача - Сумма на прямоугольнике

Решение - в конце конспект Сергея Слотина

Крутой конспект - https://archive.lksh.ru/2018/august/B'/notes/03.pdf

Так же интересный конспект от Сергея Слотина - https://ru.algorithmica.org/cs/decomposition/scanline/

Тинькофф B' - Дерево Фенвика

2022-05-17T19:56:35.233Z

#lelyte

#fenwick_tree

Дерево Фенвика - структура данных, дерево на одномерном массиве, которая обладает такими свойствами, как:

Сумма на отрезке с L по R
Изменение значения в какой-то позиции за O(LogN)
Требует O(N) памяти

Код взятия суммы на отрезке: (массив f - наше дерево)

ll get_sum(ll i){
    ll ans = 0;
    for(; i >= 0; i = (i&(i+1))-1){
        ans += f[i];
    }
    return ans;
}


ll sum_otr(ll l, ll r){
    return get_sum(r) - get_sum(l-1);
}

Обновление на точке:

void update(ll i, ll x){
    for(; i < n; i = (i | (i+1))){
        f[i] += x;
    }
}

Так же Дерево Фенвика можно сделать двумерным (подробности - https://e-maxx.ru/algo/fenwick_tree)