Global Warming
Podemos ver las temperaturas como un arreglo . Queremos decrementar un intervalo contiguo en un valor de modo que la longitud de la subsecuencia creciente más larga (LIS) sea lo más grande posible. Nótese que no hace falta considerar también incrementar, porque cada disminución de un intervalo corresponde al aumento de otro intervalo.
Subtareas 1-3: fuerza bruta
Una observación clave es que no sirve restar de un intervalo en lugar de solo para cualquier . Además, obsérvese que es óptimo restar siempre del intervalo sin importar qué.
Un algoritmo consistiría en probar por fuerza bruta todos los prefijos. Restamos de cada intervalo para todo y luego hallamos la LIS después de cada resta.
Subtarea 4: una pasada
Tomamos la LIS del arreglo. Cualquier algoritmo para hallar la LIS pasará.
Solución general
Para cada , sea la longitud de la subsecuencia creciente más larga que termina en y lo contiene, y la longitud de la subsecuencia creciente más larga que empieza en después de decrementar . Podemos calcular cada guardando la longitud de la subsecuencia decreciente más larga para cada prefijo del reverso del arreglo de entrada.
La respuesta final es .
Implementación
En la implementación es y es la variable
en el segundo bucle for.
#include <bits/stdc++.h>
using namespace std;
int temps[200005];
int pref_longest[200005];
int main() {
int n;
int x;
cin >> n >> x;
for (int i = 0; i < n; i++) { cin >> temps[i]; }
vector<int> dp(n, INT_MAX);
int longest = 0;
// longest increasing subsequence ending at i
for (int i = 0; i < n; i++) {
int j = lower_bound(dp.begin(), dp.end(), temps[i]) - dp.begin();
dp[j] = temps[i];
pref_longest[i] = j + 1;
longest = max(longest, pref_longest[i]);
}
dp = vector<int>(n, INT_MAX);
// longest decreasing subsequence ending at i of reverse
// = longest increasing subsequence starting at i
for (int i = n - 1; i >= 0; i--) {
int pos = lower_bound(dp.begin(), dp.end(), -temps[i] + x) - dp.begin();
longest = max(longest, pref_longest[i] + pos);
int insert_pos = lower_bound(dp.begin(), dp.end(), -temps[i]) - dp.begin();
dp[insert_pos] = -temps[i];
}
cout << longest << endl;
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* this code here treats the change as incrementing the suffix instead of
* decrementing the prefix as in the editorial but it's basically the same thing
*/
public class glo {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer initial = new StringTokenizer(read.readLine());
int tempNum = Integer.parseInt(initial.nextToken());
int maxCheating = Integer.parseInt(initial.nextToken());
int[] temps = Arrays.stream(read.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
// this[i] = the longest subsequence that ends at and contains temps[i]
int[] prefLongest = new int[tempNum];
ArrayList<Integer> minEndings = new ArrayList<>();
// standard LIS stuff
for (int i = 0; i < tempNum; i++) {
int t = temps[i];
int pos = bisectLeft(minEndings, t);
prefLongest[i] = pos + 1;
if (pos == minEndings.size()) {
minEndings.add(t);
} else {
minEndings.set(pos, t);
}
}
int longest = 0;
ArrayList<Integer> maxBegins = new ArrayList<>();
for (int i = tempNum - 1; i >= 0; i--) {
int t = temps[i];
// we use negatives here to keep the binary search happy
// first find the maximum increasing subsequence in the suffix that
// starts at i
int pos = bisectLeft(maxBegins, -t);
longest = Math.max(longest, prefLongest[i] + pos);
// then insert the changed temperature for later iterations
int insertPos = bisectLeft(maxBegins, -t - maxCheating);
if (insertPos == maxBegins.size()) {
maxBegins.add(-t - maxCheating);
} else {
maxBegins.set(insertPos, -t - maxCheating);
}
}
System.out.println(longest);
}
private static int bisectLeft(List<Integer> arr, int x) {
int lo = 0;
int hi = arr.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr.get(mid) < x) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
}"""
this code here treats the change as incrementing the suffix instead of
decrementing the prefix as in the editorial but it's basically the same thing
"""
from bisect import bisect_left
temp_num, max_cheating = [int(i) for i in input().split()]
temps = [int(i) for i in input().split()]
assert temp_num == len(temps)
# this[i] = the longest subsequence that ends at and contains temps[i]
pref_longest = []
min_endings = []
# standard LIS stuff
for i, t in enumerate(temps):
pos = bisect_left(min_endings, t)
pref_longest.append(pos + 1)
if pos == len(min_endings):
min_endings.append(t)
else:
min_endings[pos] = t
longest = 0
max_begins = []
for i in range(temp_num - 1, -1, -1):
t = temps[i]
# we use negatives here to keep the binary search happy
# first find the maximum increasing subsequence in the suffix that starts at i
pos = bisect_left(max_begins, -t)
longest = max(longest, pref_longest[i] + pos)
# then insert the changed temperature for later iterations
insert_pos = bisect_left(max_begins, -t - max_cheating)
if insert_pos == len(max_begins):
max_begins.append(-t - max_cheating)
else:
max_begins[insert_pos] = -t - max_cheating
print(longest)