BOJ 9623 - 부분 수열의 길이
결국 어떠한 연속된 구간의 합은 라 할 때,
이다.
를 계속 가지고가면, 를 만족하려면 여야 한다.
그럼 현재까지 본 중, 이하인 중 가장 큰 를 구하는 문제가 된다.
세그먼트 트리 풀이가 생각나서 바로 풀었는데, 를 인덱스로 가지고 값을 로 가지게끔 해서 까지 범위에서 가장 큰 인덱스를 찾아오면 된다.
이렇게 쿼리하고 정답을 갱신해준 뒤에 를 트리에 업데이트해준다.
세그 트리를 쓰면 좌표압축을 하거나 다이나믹 세그먼트 트리를 써야해서 구현이 까다로울 수 있다.
const int inf = 2e16;
// Maximum Value Dynamic Segment Tree
struct node {
int v = -inf, l = -1, r = -1;
};
struct dynamic_seg_tree {
int N, nxt = 1;
vector<node> tree;
dynamic_seg_tree(int N) : N(N) {
tree.pb({});
}
void update(int n, int nl, int nr, int i, int v) {
if (nr < i || nl > i) return;
if (nl == nr) {
tree[n].v = v;
return;
}
int m = (nl + nr) / 2;
if (i <= m) {
if (tree[n].l == -1) {
tree[n].l = nxt++;
tree.pb({});
}
update(tree[n].l, nl, m, i, v);
} else {
if (tree[n].r == -1) {
tree[n].r = nxt++;
tree.pb({});
}
update(tree[n].r, m + 1, nr, i, v);
}
tree[n].v = max(~tree[n].l ? tree[tree[n].l].v : -inf, ~tree[n].r ? tree[tree[n].r].v : -inf);
}
void update(int i, int v) {
update(0, 0, N - 1, i, v);
}
int query(int n, int nl, int nr, int l, int r) {
if (n == -1 || nr < l || nl > r) return -inf;
if (nl >= l && nr <= r) return tree[n].v;
int m = (nl + nr) / 2;
return max(query(tree[n].l, nl, m, l, r), query(tree[n].r, m + 1, nr, l, r));
}
int query(int l, int r) {
return query(0, 0, N - 1, l, r);
}
};
void solve() {
int n, x;
cin >> n >> x;
vi a(n);
fv(a);
dynamic_seg_tree seg(inf);
int sum = 0;
seg.update(inf / 2, 0);
int ans = inf;
for (int i = 0; i < n; i++) {
sum += a[i];
int ret = seg.query(0, sum - x + inf / 2);
if (ret != -inf) ans = min(ans, i - ret + 1);
seg.update(sum + inf / 2, i + 1);
}
cout << (ans == inf ? -1 : ans) << endl;
}
Comments