----> 1
a[1..n]
i
a[1..n-1] {a[1]...a[i-1],a[i+1]...a[n]}
O(1):
swap(a[n],a[i])
n--
----> 2 (рассказать минумум в очереди)
----> 3 (ровно K)
Time = O(K) * N/K = O(N)
N, K, a[1..N]
[---K---] [---K---] [---K---] [---K---]
min[i..i+K) = O(1)
suf + pref
a[0..n)
m[i + 1] = min(m[i], a[i]) = min [0..i]
m[0] = +infinity = min[0..0)
m[0] = a[0]
m[1] = min(m[0], a[1])
m[2] = min(m[1], a[2])
m[0] = +infinity
m[1] = min(a[0], m[0])
m[2] = min(a[1], m[1])
m <--- +infinity
memset(m, 0x70, sizeof(m)) // 0x707070 ~= +infinity
for i=0..n-1
for j=0..n-1
m[i + 1][j + 1] = min(m[i][j + 1], m[i + 1][j], a[i][j])
Теория: Частичные суммы
a[0..N-1]
(L, R) ---O(1)---> sum [L..R] = s[R + 1] - s[L]
s[0] = 0
s[1] = a[0] + s[0]
s[2] = a[1] + s[1]
....
s[i] = sum [0..i)
s <-- 0
for i=0..n-1
s[i + 1] = s[i] + a[i]
Обобщаем до матриц:
s <-- 0
for i=0..n-1
for j=0..n-1
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + a[i][j]
s[i][j] = sum [0..i) x [0..j)
----> 4 (отрезок с максимальной суммой)
a[0..n)
sum [l..r] --> max
r : s[r + 1] - s[l] => s[l] --> min = минимум по l=[0..r] { s[l] }
s[0] = 0
for i=0..n-1
s[i + 1] = s[i] + a[i]
pair <int, int> m[100];
m[0] = (+infinity, -1)
// m[i] = минимум по j=0..i-1 пар (s[j], j)
for i=0..n-1
m[i + 1] = min(m[i], make_pair(a[i], i))
int best = -infinity, res_l = -1, res_r = -1
for r=0..n-1
sum = s[r + 1] - m[r + 1].first // m[r + 1] = min(s[0], ... s[r])
if sum > best
best = sum
res_r = r
res_l = m[r + 1].second
---------------- (4.b) Мало памяти
Память = O(1)
int res_l = -1, res_r = -1, best = -infinity
int l = 0, sum = 0 // [l..r]
for r=0..n-1
sum += a[r]
if sum < 0
sum = 0
l = r + 1
if sum > best
best = sum, res_l = l, res_r = r
Доказательство корректности: упражнение
---------------- (4.c) Числа на окружности
O(n^2) : разрезать окружность
a[-------------]a[-------------]
length <= n
0 <= l <= r < 2n
sum [l..r] = s[r + 1] - s[l]
s[l] --> min
r - l < n
min по l = [r-n..r] if r >= n n=const
[0..r] if r < n
Time = O(n)
Упражнение: решить проще =)
---------------- (4.d) Длина отрезка от L до R
sum [l..r] = s[r + 1] - s[l]
s[l] --> min
L <= r - l + 1 <= R
1. l = [0..r] if r-R < 0 префиксы
2. l = [r-R..r-L] if r-R >= 0 константная длина R-L+1
---------------- (4.e) Длина отрезка от L до R, числа на окружности
a[-------------]a[-------------]
Свели к (4.d)
1 <= L <= R <= n
----> 5 (количество различных = max, длина не более k)
// a[i]=0..10^9
for i=0..k-1 // [0..k)
if (m[a[i]] == 0)
diff++
m[a[i]]++
int best = 0, res_r = -1
for r = k..n-1 // [r-k..r)
if diff > best
res_r = r, best = diff
// [r-k..r) --> [r-k+1..r+1) ..r]
if (m[a[r]] == 0)
diff++
m[a[r]]++
m[a[r - k]]--
if (m[a[r - k]] == 0)
diff--
----
unordered_map <int, int> m; // -std=c++11
int diff = 0
// a[i]=0..10^9
for i=0..k-1 // [0..k)
diff += (m[a[i]]++ == 0);
int best = 0, res_r = -1
for r = k..n-1 // [r-k..r)
if diff > best
res_r = r, best = diff
// [r-k..r) --> [r-k+1..r+1) ..r]
diff += (m[a[r]]++ == 0);
diff -= (--m[a[r - k]] == 0);
// O(n) * O(обращения к m) | m - массив,
// хеш-таблица (unordered_map),
// дерево поиска (map)
k=3
diff=4
1 1 1 2 2 2 3 3 3 4
l r
Упражнение: что делать, если числа отрицательные?
подсказка: sum[l..r] = s[r+1] - s[l], минимум на очереди
---> Амортизационный анализ
------------- vector
N => Time = O(N)
Time <= (N + N/2 + N/4 + ... ) + N*O(1) <= 2N + N*O(1) = O(N)
------------- последняя задача про различные числа
l=0
for r=0..n-1
while ?
l++
N => Time = O(N)
Time <= O(N) + Count(l++) = O(N) + N = O(N)
---> Амортизационный анализ: пополняемые структуры данных
a[0..n)
get(L, R) = сколько таких i, что L <= a[i] <= R
sort(a)
get(L, R) = Binary_Search(R + 1) - Binary_Search(L) // O(logn)
Binary_Search(x) : min i : a[i] >= x
Time_Build = O(NlogN)
Time_Get = O(logN)
---> Усложнение
Add: a[n++] = x
n = 2^k1 + 2^k2 + ...
a_1[k_1] // sorted
a_2[k_2] // sorted
...
a_m[k_m]
База: n=1, a1[1]
Новый Get: // m * O(logN) = O(log^2 N)
count = 0
for i=1..m
count += Get(a[i])
Переход:
Add(x) // N вызов
k_{m+1} = 1
a_{m+1} = [x]
k_i = 1
1 + 1 = 2
Build(1 + 1) // O(NlogN)
k_j = 2
Build(2 + 2) // O(NlogN)
Доказательство времени работы:
N = 2^k
Time = Build(2^k) + 2*Build(2^{k-1}) + 4*Build(2^{k-2}) + ...
Time <= (2^k + 2*2^{k-1} + 4*2^{k-2}) * logN =
(2^k + 2^k + 2^k + ...) * logN =
N * logN * logN
Общий факт:
TGet, TBuild
Новый Get = TGet * logN
Суммарное время всех Add = TBuild * logN