따끈따끈한 최신 문제입니다.
입력으로 최대 10만 개의 블록이 주어지고 그 블록들이 모두 쌓였을 때 최대 높이를 구하는 문제입니다.
우선 완전 탐색으로 접근하게 되면 블록을 한번 놓을 때마다
그 블록의 범위를 확인하며 쌓인 블록들 중에 그 범위 안에 있는 블록들의 높이를
확인하며 답을 구하면 됩니다.
하지만 시간 복잡도가 O(N^2)이라 시간 초과가 납니다.
그럼 시간을 줄여야 하는데 범위 안에 있는 블록들의 높이를 확인하는 시간을 O(lgN)으로 줄일 수 있을 것 같습니다.
주어진 구간 안에 높이의 최댓값을 확인하는 쿼리를 가진 세그먼트 트리를 이용하면 됩니다.
블록을 하나씩 쌓기 전에 그 블록의 범위 안에 그전에 쌓여있던 블록들의 높이의 최댓값을 구한 후
그 블록을 세그먼트 트리에 블록의 왼쪽부터 오른쪽까지 업데이트를 해주면 됩니다.
구간 업데이트를 사용해야 하므로 레이지 프로퍼게이션을 사용하면 됩니다.
구간 업데이트를 하기 전에 1 <= W, D <= 10^9이므로 최대 좌표 범위가 1 ~ 2 * 10^9입니다.
이 좌표들을 세그먼트 트리에 저장하려면 메모리가 부족하기 때문에
좌표 압축을 하여 세그먼트 트리에 저장을 하겠습니다.
최대 좌표는 20억이지만 주어지는 좌표는 왼쪽 오른쪽 합하여 20만 개이기 때문에
좌표들을 입력받고 정렬을 해준 다음 이분 탐색을 하여 좌표를 찾아주시면 됩니다.
코드를 보시면 이해가 쉬울 것 같습니다.
쿼리 함수는 높이의 최댓값을 구하는 쿼리를 구현하면 됩니다.
그렇게 되면 블록을 쌓기 전 그 블록 범위 쿼리를 하면 그 범위 안에 최대 높이가 나올 것이고
그 위에 쌓는 것이므로 구한 최대 높이 + 1을 업데이트를 해주시면 됩니다.
이 과정을 진행 중에 구하는 높이들 중 최대를 구하면 답을 구할 수 있습니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define vi vector <int>
#define vvi vector <vi>
#define pii pair <int,int>
using namespace std;
struct LST {
int* tree, * lazy;
int size;
LST(int n) {
size = (1 << (int)(ceil(log2(n)) + 1));
tree = new int[size]();
lazy = new int[size]();
}
void propagate(int now, int s, int e) {
if (!lazy[now]) return;
tree[now] = max(tree[now], lazy[now]);
if (s < e) {
lazy[now * 2] = max(lazy[now * 2], lazy[now]);
lazy[now * 2 + 1] = max(lazy[now * 2 + 1], lazy[now]);
}
lazy[now] = 0;
}
void update(int now, int s, int e, int l, int r, int val) {
propagate(now, s, e);
if (r < s || e < l) return;
if (l <= s && e <= r) {
lazy[now] = max(lazy[now], val);
propagate(now, s, e);
return;
}
int mid = (s + e) / 2;
update(now * 2, s, mid, l, r, val);
update(now * 2 + 1, mid + 1, e, l, r, val);
tree[now] = max(tree[now * 2], tree[now * 2 + 1]);
}
int query(int now, int s, int e, int l, int r) {
propagate(now, s, e);
if (r < s || e < l) return 0;
if (l <= s && e <= r) return tree[now];
int mid = (s + e) / 2;
return max(query(now * 2, s, mid, l, r), query(now * 2 + 1, mid + 1, e, l, r));
}
~LST() {
delete[] tree;
delete[] lazy;
}
};
int main() {
FIO;
int n; cin >> n;
vector <pii> v(n);
vi idx(2 * n);
FOR(i, 0, n - 1) {
int a, b; cin >> a >> b;
v[i] = { b,b + a - 1 };
idx[i * 2] = b, idx[i * 2 + 1] = b + a - 1;
}
sort(all(idx));
auto find_idx = [&](int x) {return lower_bound(idx.begin(), idx.end(), x) - idx.begin(); };
LST lst(2 * n);
int ans = 0;
FOR(i, 0, n - 1) {
pii now = v[i];
int a = find_idx(now.first), b = find_idx(now.second);
int c = lst.query(1, 1, 2 * n, a, b);
ans = max(ans, c + 1);
lst.update(1, 1, 2 * n, a, b, c + 1);
}
cout << ans << '\n';
return 0;
}