백준 9623 - 부분 수열의 길이

부분 수열의 길이

풀이

주어진 배열의 누적합을 구해서 max segment tree에 넣는다.

target을 찾고 싶다고 하자.

1. if target <= tree[2*node] 이라면, $2\times node$에서 구하면 된다.
2. else, $2 \times node + 1$에서 구한다.
3. start == end라면(자식 노드가 없다면), start를 반환한다.

모든 시작 인덱스에서부터 검사해야 하므로 i번째부터 시작한 연속 부분수열을 찾고 싶다면 target에 psum[i-1]을 더해주면 된다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, a, b) for(ll i=(a); i<(b); i++)
#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define Bor(i, a, b) for(ll i=(a); i>(b); i--)
#define BOR(i, a, b) for(ll i=(a); i>=(b); i--)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

class Segment {
public:
    vector<ll> tree; //tree[node] := a[start ~ end] 의 합

    Segment() {}
    Segment(int size) {
        this->resize(size);
    }
    void resize(int size) {
        size = (int) floor(log2(size)) + 2;
        size = pow(2, size);
        tree.resize(size, 0);
    }
    ll init(vector<ll> &a, int node, int start, int end) {
        if(start == end) return tree[node] = a[start];
        else return tree[node] = max(init(a, 2 * node, start, (start + end) / 2),
                                     init(a, 2 * node + 1, (start + end) / 2 + 1, end));
    }
    ll find(int node, int start, int end, int left, int right, ll target) {
        if(right < start or end < left) return INF;
        if(tree[node] < target) return INF;
        if(start == end) return start;
        if(left <= start and end <= right) {
            if(tree[2*node] >= target) return find(2*node, start, (start+end)/2, left, right, target);
            else return find(2*node+1, (start+end)/2+1, end, left, right, target);
        }
        else {
            return min(find(2*node, start, (start+end)/2, left, right, target),
                       find(2*node+1, (start+end)/2+1, end, left, right, target));
        }
    }
};

void solve() {
    ll n, x; cin >> n >> x;
    vector<ll> a(n+1,0), psum(n+1,0);
    FOR(i,1,n) {
        cin >> a[i];
        psum[i] = psum[i-1] + a[i];
    }
    Segment seg(n);
    seg.init(psum,1,1,n);

    ll ans = INF;
    FOR(i,1,n) {
        ll res = seg.find(1,1,n,i,n,x + psum[i-1]);
        if(res != INF and psum[res] >= x+psum[i-1]) ans = min(ans, res-i+1);
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int TC=1;
    cin >> TC;
    FOR(tc, 1, TC) {
//        cout << "Case #" << tc << ": ";
        solve();
    }


    return 0;
}