백준13050 Maximal Sum

작성일 | In

문제 링크

  • http://icpc.me/13050

사용 알고리즘

  • Segment Tree

풀이

각 b[i]마다, b[i]보다 작거나 같은 원소들만 a 배열에 남겨놓은 다음에 a배열에서 합이 최대인 subarray를 고를 것 입니다.
합이 최대인 subarray의 합을 세그먼트 트리로 구한다고 합시다. b[i]보다 작은 원소들만 남겨놓는 작업을 효율적으로 처리해야 합니다.

b[i]를 오름차순으로 정렬을 한 다음에 오프라인으로 처리를 하면, a의 각 원소는 세그먼트 트리에 최대 1번만 들어가고 세그먼트 트리에서 나오는 일은 없습니다.
그러므로 update는 최대 n번, query는 최대 m번 발생하기 때문에 O((n+m) log n)에 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
const ll inf = 1e18;
const int bias = 1 << 17;

ll lv[2*bias];
ll rv[2*bias];
ll sv[2*bias];
ll mv[2*bias];

void update(int x, ll v){
    x |= bias;
    lv[x] = rv[x] = sv[x] = mv[x] = v;
    while(x >>= 1){
        sv[x] = max(-inf, sv[x << 1] + sv[x << 1 | 1]);
        lv[x] = max(lv[x << 1], sv[x << 1] + lv[x << 1 | 1]);
        rv[x] = max(rv[x << 1 | 1], sv[x << 1 | 1] + rv[x << 1]);
        mv[x] = max({mv[x << 1], mv[x << 1 | 1], rv[x << 1] + lv[x << 1 | 1]});
    }
}

ll a[101010], b[101010];
ll ans[101010];

struct asdf{
    ll v, q, idx;
    bool operator < (const asdf &t) const {
    	if(v != t.v) return v < t.v;
    	if(q != t.q) return q < t.q;
    	return idx < t.idx;
    }
};
int pv;
vector<asdf> q;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i], q.push_back({a[i], 0, i});
    for(int i=1; i<=m; i++) cin >> b[i], q.push_back({b[i], -1, i});

    for(int i=0; i<bias; i++) update(i, -inf);

    sort(q.begin(), q.end()); reverse(q.begin(), q.end());
    for(auto i : q){
        ll v = i.v;
        ll t = i.q;
        ll idx = i.idx;
        if(t == 0){
            update(idx, v);
        }else{
            ans[idx] = mv[1];
            if(mv[1] < -inf/2) ans[idx] = 0;
        }
    }
    for(int i=1; i<=m; i++) cout << ans[i] << " ";
}