1) Операционные системы

1.1) Удаляем все системы, чье начало от l до r 

Хотим добавить (4, 10):

Сейчас есть (1, 3), (3, 4), (5, 5), (6, 8), (10, 10), (11, 13)

Вызываем lower_bound и идем циклом, пока не увидим систему с большим началом 

1.2) Надо удалить что-то еще

Удалили все с началами от l до r 
Если у системы начало > r - то удалять ее не надо

Если начало меньше l - то надо удалить, если конец >= l

Но таких систем не может быть две 

1.3) Можно сделать еще один сет для концов(не надо)

Просто посмотреть на предыдущий от lowerbound(иначе он бы залезал на систему)


vector<pair<int,int>> a(n);

set<begin, ind> s1;
set<end, ind> s2; - полезная конструкция

2) Гистограмма: 


В стеке храним пары (индекс, высота)

Идем по возрастанию высот, пихаем пары в стек 


1 4 5 6 2

Stack = (6, 5, 4, 1) - было возрастание 

Встретили единичку, начинаем распаковывать стек 
Пересчитываем прямоугольники(6), (6, 5), (6, 5, 4)

1 < 2 - добавляем в верхушку стека 2, получаем стек = (2, 1)


1  2  3  4  5 
2, 3, 4, 5, 4

Был стек (5, 4, 3, 2)

Вынули пятерку, релаксировали ответ прямоугольник из пятерки (5)
Увидели 4 - переходим на следующую итерацию, стек такой же ((2, 4), (1, 3), (0, 2))



3) Генерация: 

vector<vector<int>> ans(складываем сюда все)

void gen(vector<int> cur){
	if (cur.size() == n){
		ans.push_back(cur);
		return;
	}
	for (int i = 1; i <= n; i++){
		cur.push_back(i); //cur = {1, 1}, cur = {1, 2}, cur = {1, 3}
		gen(cur);
		cur.pop_back(); //cur = {1}, cur = {1}
	}
}



4) Квадраты и кубы:


Перебираем y | y^3 от a до b (1e6)

Хотим посчитать количество х таких, что x^2 >= (y^3 - k) и x^2 <= (y^3 + k)

[l, r]

1) Нам нужно найти минимальный квадрат, который >= l 

2) Нам нужно найти максимальный квадрат, который <= r


l, r 
while (l < r - 1){
	int m = (l + r) / 2;
	if (m * m >= l){
		r = m;
	}
	else{
		l = m;
	}
}


5) Динамика:


Есть лесенка, можно прыгать через одну ступеньку и на следующую ступеньку, сколько вариантов 
допрыгать с 1 по n 


1) Dp[i] - что это значит? количество вариантов допрыгать с 1 ступеньки до i-й 
2) База динамики - стартовые значения, которые не будут считаться в основном цикле  
3) Переход - формула, чтобы считать динамику
dp[i] - могли сюда припрыгать либо с i - 1-й ступеньки, либо с i - 2-й
dp[i] = dp[i - 1] + dp[i - 2]
4) Где хранится ответ? dp[n - 1]
5) Порядок пересчета - когда мы хотим считать dp[i], все значения, которые входят в формулу подсчета, 
уже должны быть посчитаны 

dp[0] = 1;
dp[1] = 1;
for (i = 2; i < n; i++){
	dp[i] = dp[i - 1] + dp[i - 2];
}


НВП - наибольшая возрастающая подпоследовательность 

a[n] = [1, 3, 4, 5, 7, 3, 4, 7]


1) dp[i] - длина наибольшей воз.подпоследовательности, которая кончается в a[i] 

2) dp[0] = 1

3) 

0 1 2 3 4 
1 2 3 8 4

dp[4] = 1


Определение подпоследовательности массива - (a_1, a_2, a_3...), эти элементы есть в массиве 
и идут в таком же порядке 

Переход - давай переберем предыдущий элемент подпоследовательности 

j < i, a[j] < a[i] - только такой элемент может быть предыдущим 

Чтобы считать dp[i]:

for (j = 0; j < i; j++){
	dp[i] = 1;
	if (a[j] < a[i]){
		dp[i] = max(dp[i], dp[j] + 1);
	}
}

Где лежит ответ на задачу? Это максимальное dp[i]

В дп есть восстановление ответа

Допустим, надо непосредственно саму НВП(не только ее длину)

p[i] - это индекс j, откуда мы пришли 

for (j = 0; j < i; j++){
	dp[i] = 1;
	p[i] = -1;
	if (a[j] < a[i]){
		if (dp[j] + 1 > dp[i]){
			p[i] = j;
		}
		dp[i] = max(dp[i], dp[j] + 1);
	}
}



Ответ лежит в cur 

while (p[cur] != -1){
	ans.push_back(a[cur]);
	cur = p[cur];
}