BOJ 9623 - 부분 수열의 길이

BOJ 9623 - 부분 수열의 길이

결국 어떠한 연속된 구간의 합은 $S[i]=\sum_{k=0}^i A[k]$ 라 할 때,

$S[i]-S[j]~(j < i)$ 이다.

$S[i]$ 를 계속 가지고가면, $S[i]-S[j] \ge X$를 만족하려면 $S[i]-X \ge S[j]$ 여야 한다.

그럼 현재까지 본 $S[j]$ 중, $S[i]-X$ 이하인 $j$ 중 가장 큰 $j$를 구하는 문제가 된다.

세그먼트 트리 풀이가 생각나서 바로 풀었는데, $S[j]$ 를 인덱스로 가지고 값을 $j$ 로 가지게끔 해서 $-\infty \sim S[i]-X$ 까지 범위에서 가장 큰 인덱스를 찾아오면 된다.

이렇게 쿼리하고 정답을 갱신해준 뒤에 $(S[i], i)$ 를 트리에 업데이트해준다.

세그 트리를 쓰면 좌표압축을 하거나 다이나믹 세그먼트 트리를 써야해서 구현이 까다로울 수 있다.

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;  
}