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

В холле 179 школы, есть информационный стенд размером H×W (H – высота, W – ширина). На этом стенде размещается информация о кружках, изменениях в расписании, победах в олимпиадах, а также другая важная информация.

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

Каждое объявление представляет собой полоску бумаги единичной высоты. I-ое объявление представляет собой прямоугольник размером 1×W_i.

Когда кто-либо вешает объявление на стенд, то он старается повесить объявление как можно выше. Среди возможных верхних мест всегда выбирается самое левое. Если подходящего места для объявления не нашлось, то объявление не вешается на стенд. Ваша задача состоит в том, чтобы для каждого объявления определить, как высоко оно будет располагаться (в каком ряду).

Входные данные
Первая строка содержит три целых числа H, W и N (1≤H,W≤10⁹; 1≤N≤200000) — размеры стенда и количество объявлений. Каждая из следующих N строк содержит по одному целому числу W_i (1≤W_i≤10⁹) — ширину i-го объявления.

Выходные данные
Для каждого из объявлений (в порядке следования во входном файле) выведите номер ряда, в котором оно будет размещено. Ряды занумерованы от 1 до H сверху вниз. Если объявление разместить нельзя — выведите «–1».

Костя и Женя — создатели группы <<Бумага>> — после выпуска легендарного альбома решили создать новое музыкальное объединение <<дневные грузчики>>, для этого им нужно найти двух новых людей.

Они пригласили на кастинг \(n\) человек. Кастинг продлится \(q\) дней. В \(i\)-й из дней Костя и Женя хотят найти двух человек на отрезке с \(l_i\) по \(r_i\), которые больше всего подходят их объединению. Так как <<дневные грузчики>> занимаются современным искусством,  музыкальные навыки им не важны, и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.

Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!

Формат входных данных
В первой строке вам дано два числа \(n, q\) (\(2 \leqslant n \leqslant 4 \cdot 10^5, 1 \leqslant q \leqslant 10^6\)) — количество людей, которые пришли на кастинг, а также количество дней кастинга.

Во второй строке вам даны \(n\) чисел \(a_1, a_2, a_3, \ldots, a_n\) (\(1 \leqslant a_i \leqslant n\)) — рост каждого из кандидатов.

Также гарантируется, что все \(a_i\) различны.

В следующих \(q\) строках даны по \(2\) числа \(l_i, r_i\) (\(1 \leqslant l_i < r_i \leqslant n\)) — отрезок людей для рассмотрения в \(i\)-й день кастинга.

Формат выходных данных
Выведите \(q\) строк. В \(i\)-й строке должна быть минимальная разница роста между двумя кандидатами на отрезке в \(i\)-й день кастинга.

Примечание
В первом примере минимальная разность на отрезке \([1, 2]\) составляет \(2\) (\(3 - 1 = 2\)), на отрезке \([2, 3]\) – \(1\), на отрезке \([1, 3]\) также \(1\).

В третьем примере минимальную разность на отрезке \([4, 6]\) составляют числа \(3, 5\) (\(5 - 3 = 2\)). На отрезке \([1, 2]\) минимальную разность имеют числа \(2, 6\) (\(6 - 2 = 0\)). На отрезке \([3, 6]\) минимальную разность имеют числа \(1, 3\) (\(3 - 1 = 2\)). На отрезке \([1, 3]\) минимальную разность образуют числа \(1, 2\) (\(2 - 1 = 1\)).

На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из \(n\) чисел.

В частности, вы интересуетесь так называемой равномерностью массива. Предположим, что в массиве число \(b_1\) встречается \(k_1\) раз, \(b_2\) — \(k_2\) раз, и т.д. Тогда равномерностью массива называется такое минимальное целое число \(c \ge 1\), что \(c \ne k_i\) для любого \(i\).

В рамках вашего исследования вы хотите последовательно проделать \(q\) операций.

• Операция \(t_i = 1\), \(l_i\), \(r_i\) задаёт запрос исследования. Необходимо вывести равномерность массива, состоящего из элементов на позициях от \(l_i\) до \(r_i\) включительно.

• Операция \(t_i = 2\), \(p_i\), \(x_i\) задаёт запрос уточнения данных. Начиная с этого момента времени \(p_i\)-му элементу массива присваивается значения \(x_i\).

Формат входных данных
Первая строка содержит \(n\) и \(q\) (\(1 \le n, q \le 100\,000\)) — размер массива и число запросов соответственно.

Во второй строке записаны ровно \(n\) чисел — \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(1 \le a_i \le 10^9\)).

Каждая из оставшихся \(q\) строк задаёт очередной запрос.

Запрос первого типа задаётся тремя числами \(t_i = 1\), \(l_i\), \(r_i\), где \(1 \le l_i \le r_i \le n\) — границы соответствующего отрезка.

Запрос второго типа задаётся тремя числами \(t_i = 2\), \(p_i\), \(x_i\), где \(1 \le p_i \le n\) — позиция в которой нужно заменить число, а \(1 \le x_i \le 10^9\) — его новое значение

Формат выходных данных
Для каждого запроса первого типа выведите одно число — равномерность соответствующего отрезка массива.

Первый запрос состоит из ровно одного элемента — \(1\). Минимальное подходящее \(c = 2\).

Отрезок второго запроса состоит из четырёх \(2\), одной \(3\) и двух \(1\). Минимальное подходящее \(c = 3\).

Отрезок четвёртого запроса состоит из трёх \(1\), трёх \(2\) и одной \(3\). Минимальное подходящее \(c = 2\).

 

Коренной житель Снежинска Даня Багров уже подрос, и пришло время найти работу. Конечно же, Даня захотел устроиться на завод.
Так как большинство заводов расположены в Челябинске (там их более 60), Снежинску достался всего один, и, соответственно, спрос на такое желаемое место работы очень высок в этом городе, поэтому при устройстве на завод в Снежинске все сотрудники в обязательном порядке должны решить задачу по программированию.
Даня прогуливал в детстве информатику, поэтому с программированием у него всё плохо. Помогите Дане решить задачку, чтобы он смог без проблем устроиться на завод и жить в достатке.
Дано два массива целых чисел a₁,a₂,...,a_n и b₁,b₂,...,b_n и q запросов двух типов:
•    1 l r x — нужно сделать a_i = x для всех l <= i <= r.
•    2 l r — нужно найти минимальное значение \( {lcm (a_i,b_i)\over gcd(a_i,b_i)}\)  по всем l <= i <= r.
Входные данные
В первой строке находятся два целых числа n и q (1 <= n,q <= 5 · 10⁴) — количество чисел в массивах a и b и количество запросов.
Во второй строке находятся n целых чисел a₁,a₂,...,a_n (1 <= a_i <= 5 · 10⁴).
В третьей строке находятся n целых чисел b₁,b₂,...,b_n (1 <= b_i <=5  · 10⁴).
Далее следует q строк, j-я из которых начинается с целого числа t (1 <= t <= 2) и означает, что j-й запрос относится к типу t.
Если t =1, то остальная часть строки содержит целые числа l, r и x (1 <= l <= r <= n, 1 <= x <= 5·10⁴). Если t =2, то остальная часть строки содержит целые числа l и r (1 <= l <= r <= n).
Выходные данные
Для каждого запроса второго типа выведите ответ на задачу. Гарантируется, что хотя бы один такой запрос будет.
 

Примеры

№	Входные данные	Выходные данные
1	10 10 6 10 15 4 9 25 2 3 5 30 1 2 3 4 6 9 12 15 18 30 2 1 10 1 7 10 9 2 5 10 1 1 6 14 2 4 7 2 3 9 1 2 9 30 2 1 4 2 3 7 2 5 10	1 2 12 2 10 5 2

Дана перестановка из n элементов.
Ответьте на m запросов про число инверсий для подотрезка перестановки от l до r.
Инверсией называется пара индексов i, j такая, что i < j и a_i > a_j, где a_i - это i-й элемент перестановки.

Входные данные:
В первой строке задано число n (1 <= n <= 10⁵).
Во второй строке задана перестановка из n элементов (элементы перестановки - попарно различные целые числа от 1 до n).
В третьей строке задано число m (1 <= m <= 10⁵).
В последующих m строках содержится по два числа l и r - границы запроса (1 <= l, r <= n).

Выходные данные:
Выведите m строк - ответы на данные запросы.

Примеры:
 

Входные данные	Выходные данные
5 4 5 2 3 1 3 1 3 3 5 1 5	2 2 8
6 5 2 4 3 1 6 3 4 6 2 5 1 5	1 4 8

У Эвана есть любимое число k и массив a_i длины n. Теперь он просит вас ответить на m запросов.

Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел a_i, a_i + 1, ..., a_j равен k.

Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤ 10⁶) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ a_i ≤ 10⁶) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа l_i и r_i (1 ≤ l_i ≤ r_i ≤ n), определяющие i-й запрос.

Выходные данные:
Выведите m строк, ответы на запросы в порядке их появления во входных данных.

Примеры:
 

Входные данные	Выходные данные
6 2 3 1 2 1 1 0 3 1 6 3 5	7 0
5 3 1 1 1 1 1 1 1 5 2 4 1 3	9 4 4

Имеется массив натуральных чисел a₁, a₂, ..., a_n. Рассмотрим некоторый его подмассив a_l, a_l + 1, ..., a_r, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через K_s число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений K_s·K_s·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.

Необходимо вычислить мощности каждого из t заданных подмассивов.

Входные данные
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ a_i ≤ 10⁶) — элементы массива.
Следующие t строк содержат по два натуральных числа l и r (1 ≤ l ≤ r ≤ n) — индексы левого и правого концов соответствующего подмассива.

Выходные данные
Выведите t строк, где i-ая строка содержит единственное натуральное число — мощность подмассива i-го запроса.

Примеры:
 

Входные данные	Выходные данные
3 2 1 2 1 1 2 1 3	3 6
8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7	20 20 20

Вам дан массив целых чисел А длиной n.
Необходимо ответить на m запросов вида "сообщите количество различных чисел подотрезка массива А от элемента с индексом l до элемента с индексом r" (обе границы подотрезка включены, массив нумеруется с единицы).

Входные данные:
В первой строке дано два числа: n - количество элементов массива и m - количество запросов (1 <= n, m <= 10⁵).
Во второй строке дано n целых чисел A_i - элементы массива (0 <= A_i <= 10⁶).
Далее дано m строк, в каждой по два числа l и r - границы подотрезка для каждого запроса (1 <= l <= r <= n).

Выходные данные:
В единственной строке выведите через пробел m чисел - для каждого запроса количестве различных чисел на соответствующем подотрезке.

Пример:
 

Входные данные	Выходные данные
7 5 1 3 1 2 2 4 1 1 3 4 5 3 7 2 4 7 7	2 1 3 3 1

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

№	Входные данные	Выходные данные
1	7 abcdbcc	3
2	4 bbcb	2

Реализуйте структуру данных для эффективного вычисления максимумов подряд идущих элементов массива.

Входные данные
В первой строке вводится одно натуральное число N (\(1 <= N <= 100000\)) — количество чисел в массиве. Во второй строке вводятся N чисел от 1 до 100000 — элементы массива. В третьей строке вводится одно натуральное число K (\(1 <= K <= 30000\)) — количество запросов на вычисление максимума. В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

Выходные данные
Для каждого запроса выведите значение максимального элемента на указанном отрезке массива. Числа выводите в одну строку через пробел.

 

Примеры

№	Входные данные	Выходные данные
1	5 2 2 2 1 5 2 2 3 2 5	2 5

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

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

int K;

struct query
{
    int l, r, ind;
};

bool cmp(query a, query b)
{
    if (a.l / K != b.l / K)
        return a.l / K < b.l / K;
    else
        return a.r < b.r;
}

int main()
{
    int n, q;
    cin >> n >> q;
    // для простоты, считайте, что q = n
    K = (int)sqrt(n);

    vector <int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    vector <query> ask(q);
    vector <int> ans(q);
    for (int i = 0; i < q; i++)
    {
        cin >> ask[i].l >> ask[i].r;
        ask[i].l--; ask[i].r--;
        ask[i].ind = i;
    }
    sort(ask.begin(), ask.end(), cmp);

    // Посчитайте асимптотику только части кода, 
    // расположенной ниже этого комментария

    int sum = 0, L = ask[0].l, R = ask[0].r;
    for (int i = ask[0].l; i <= ask[0].r; i++)
        sum += arr[i];
    ans[ask[0].ind] = sum;

    for (int i = 1; i < q; i++)
    {
        for (int j = L; j < ask[i].l; j++)
            sum -= arr[j];
        for (int j = L - 1; j >= ask[i].l; j--)
            sum += arr[j];
        for (int j = R + 1; j <= ask[i].r; j++)
            sum += arr[j];
        for (int j = R; j > ask[i].r; j--)
            sum -= arr[j];
        ans[ask[i].ind] = sum;
        L = ask[i].l; R = ask[i].r;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << endl;

    return 0;
}

1) каждая итерация O(sqrt(n))       
2) суммарно O(nsqrt(n))     
3) каждая итерация O(logn)       
4) суммарно O(nlogn)

Дан массив a длины n (\(1 <= n <= 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида +, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)) и запросов вида ?, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)).

В первом случае нужно добавить к числам на отрезке от l до r включительно, число k.
Во втором случае нужно вывести 1, если на отрезке от l до r включительно, есть число k, иначе вывести 0.

Элементы нумеруются с 1 до n.

Гарантируется, что после любого запроса любой элемент массива a лежит в диапазоне от \(-10^9\) до \(10^9\) включительно.

 

Примеры

№	Входные данные	Выходные данные
1	5 1 2 1 1 3 3 ? 1 4 3 + 2 3 2 ? 1 4 3	0 1

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида *, l, r, k (\(1 <= l <= r <= n\), \(0 <= k <10\)) и запросов вида ?, i (\(1 <= i <= n\)).

В первом случае нужно умножить числа на отрезке от l до r включительно на k.

Во втором случае нужно вывести число, стоящее на позиции i.

Элементы нумеруются с 1 до n.

 

Примеры

№	Входные данные	Выходные данные
1	5 1 1 1 1 1 3 ? 3 * 2 3 9 ? 3	1 9

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Если \(t = 0\), то на запрос нужно вывести сумму чисел на отрезке от l до r включительно. Если \(t = 1\), то элементу с номером l присваивается значение r. Элементы нумеруются с 1 до n. 

 

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 4 5 4 0 1 2 1 1 5 0 1 2 0 1 1	3 7 5

Во Флатландии протекает богатая рыбой река Большой Флат. Много лет назад река была поделена между n рыболовными предприятиями, каждое из которых получило непрерывный отрезок реки. При этом i-е предприятие, если рассматривать их по порядку, начиная от истока, изначально получило отрезок реки длиной ai .

С тех пор с рыболовными предприятиями во Флатландии k раз происходили различные события. Каждое из событий было одного из двух типов: банкротство некоторого предприятия или разделение некоторого предприятия на два.

При некоторых событиях отрезок реки, принадлежащий предприятию, с которым это событие происходит, делится на две части. Каждый такой отрезок имеет длину большую или равную 2. Деление происходит по следующему правилу. Если отрезок имеет четную длину, то он делится на две равные части. Иначе он делится на две части, длины которых различаются ровно на единицу, при этом часть, которая ближе к истоку реки, имеет меньшую длину.

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

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

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

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

Формат входного файла
Первая строка входного файла содержит два целых числа: n и p — исходное количество предприятий (2 ≤ n ≤ 100 000) и номер подзадачи (0 ≤ p ≤ 4). Вторая строка входного файла содержит n целых чисел a1, a2, …, an — длины исходных отрезков реки. Третья строка входного файла содержит целое число k — количество событий, происходивших с предприятиями (1 ≤ k ≤ 100 000). Последующие k строк содержат описания событий, i-я строка содержит два целых числа: ei и vi — тип события и номер предприятия, с которым оно произошло. Значение ei = 1 означает, что предприятие, которое после всех предыдущих событий является vi-м по порядку, если считать с единицы от истока реки, обанкротилось, а значение ei = 2 означает, что это предприятие разделилось на два. Гарантируется, что значение vi не превышает текущее количество предприятий. Гарантируется, что если отрезок предприятия при банкротстве или разделении требуется поделить на две части, то он имеет длину большую или равную 2. Гарантируется, что если на реке осталось единственное предприятие, оно не банкротится.

Формат выходного файла
Выходной файл должен содержать (k + 1) целых чисел, по одному в строке. Первая строка должна содержать исходную сумму квадратов длин отрезков реки, а каждая из последующих k строк — сумму квадратов длин отрезков реки после очередного события.

Пример
Ввод:
4 0
3 5 5 4
5
1 1
2 1
1 3
2 2
1 3
Вывод:
75
105
73
101
83
113

Пояснение к примеру
Распределение отрезков реки между предприятиями после каждого события, описанного в примере, приведено на рисунке ниже.