문제 링크 : https://www.acmicpc.net/problem/13557
문제 태그
Segment Tree
문제 소개
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
- x1 y1 x2 y2: x1 ≤ i ≤ y1, x2 ≤ j ≤ y2, i ≤ j인 모든 (i, j)에 대해서 Ai + ... + Aj의 최댓값을 출력한다. (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ N, x1 ≤ y1, x2 ≤ y2)
문제 풀이
주어진 구간 내에서 최대 부분합을 구하는 문제는 Segment Tree를 이용해서 풀 수 있음이 잘 알려져 있다. 특히 "금광 세그"라고 불리는 테크닉이다. 이 부분에 대해서는 이 글 을 참조하자.
관찰 1. 이 문제에서 값은 변하지 않는다. 따라서 prefix sum을 들고 있으면 구간 합을 O(1)만에 구할 수 있다.
관찰 1-2. 문제에서 두 개의 구간은 아예 겹치지 않을 때라고 생각을 하고 문제를 풀어보자. 어떤 시작점의 범위와 끝 점의 범위가 정해진 상태에서 구간의 최댓값은 어떻게 될까? 구간의 합은 끝 점에 대한 prefix sum - 시작전 점에 대한 prefix sum으로 표현이 된다. 따라서 prefix sum들이 쭉 있을때, 시작점의 범위에서는 구간의 최솟값을 찾으면 되고, 끝점의 범위에서는 구간의 최댓값을 찾으면 된다는 것이다.
이제 구간을 겹쳐보자. 위에서 생각한 것과 똑같이 시작점의 구간에서 최솟값을 찾고 끝점의 구간에서 최댓값을 찾으면 된다. 하지만 여기서 문제가 발생한다. 끝점은 시작점의 뒤에 있어야 하는데, 구간이 겹치기 때문에 시작점이 끝점보다 뒤에 있을 수 있다는 것이다. 따라서 이를 경우의 수로 나눠서 해결할 것이다.
시작점으로만 가능한 구간을 구간1이라고 하자. 시작점과 끝점 둘 다 가능한 구간을 구간 2라고 하자. 끝점만 가능한 구간을 구간 3이라고 하자. 그러면 두 점의 위치로 가능 한 경우는 (1,2) (2,2) (1,3) (2,3)이다. 이때 (1,2),(1,3),(2,3)은 두 점 간의 순서관계가 뒤집힐 일이 없다. 따라서 위에서 설명한 것처럼 prefix로 만든 세그트리를 이용해 구간 최소, 구간 최대를 잡는 것을 해결할 수 있다.
점이 (2,2)에 있을 때는 순서관계를 고려해야하며 이는 2번 구간 내에서 최대 부분합을 구하는 문제와 동치이다. 따라서 맨 처음에 설명한 "금광 세그"라고 불리는 테크닉을 활용하여 문제를 해결할 수 있다.
코드
|
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll arr[101010];
ll pre[101010];
ll tmin[401010];
ll tmax[401010];
struct Node{
ll all,lans,rans,ans;
};
Node tree[404040];
ll init1(ll s,ll e,ll nod){
if(s==e) return tmin[nod]=pre[s];
return tmin[nod]=min(init1(s,(s+e)/2,nod*2),init1((s+e)/2+1,e,nod*2+1));
}
ll sol1(ll l,ll r,ll s,ll e,ll nod){
if(r<s||l>e) return 1e18;
if(l<=s&&e<=r) return tmin[nod];
return min(sol1(l,r,s,(s+e)/2,nod*2),sol1(l,r,(s+e)/2+1,e,nod*2+1));
}
ll init2(ll s,ll e,ll nod){
if(s==e) return tmax[nod]=pre[s];
return tmax[nod]=max(init2(s,(s+e)/2,nod*2),init2((s+e)/2+1,e,nod*2+1));
}
ll sol2(ll l,ll r,ll s,ll e,ll nod){
//printf("%lld %lld %lld %lld %lld\n",l,r,s,e,nod);
if(r<s||l>e) return -1e18;
if(l<=s&&e<=r) return tmax[nod];
return max(sol2(l,r,s,(s+e)/2,nod*2),sol2(l,r,(s+e)/2+1,e,nod*2+1));
}
Node mergee(Node a,Node b){
Node x;
x.all=a.all+b.all;
x.ans=max({a.ans,b.ans,a.rans+b.lans});
x.lans=max(a.lans,a.all+b.lans);
x.rans=max(b.rans,b.all+a.rans);
return x;
}
Node init3(ll s,ll e,ll nod){
if(s==e) return tree[nod]={arr[s],arr[s],arr[s],arr[s]};
Node a=init3(s,(s+e)/2,nod*2);
Node b=init3((s+e)/2+1,e,nod*2+1);
return tree[nod]=mergee(a,b);
}
Node sol3(ll l,ll r,ll s,ll e,ll nod){
Node x;
if(r<s||l>e||l>r) return x={-1e15,-1e15,-1e15,-1e15};
if(l<=s&&e<=r) return tree[nod];
return mergee(sol3(l,r,s,(s+e)/2,nod*2),sol3(l,r,(s+e)/2+1,e,nod*2+1));
}
int main(){
ll i,j,k,l,m,n;
scanf("%lld",&n);
for(i=1;i<=n;i++){
scanf("%lld",&arr[i]);
pre[i]=pre[i-1]+arr[i];
}
init1(0,n,1);
init2(0,n,1);
init3(1,n,1);
ll x1,x2,y1,y2,t;
scanf("%lld",&t);
while(t--){
scanf("%lld %lld %lld %lld",&x1,&x2,&y1,&y2);
ll ans1,ans2,ans3;
ans1=sol2(y1,y2,0,n,1)-sol1(x1-1,min(y1,x2)-1,0,n,1);
ans2=sol2(max(x2,y1),y2,0,n,1)-sol1(x1-1,x2-1,0,n,1);
ans3=sol3(y1,x2,1,n,1).ans;
printf("%lld\n",max({ans1,ans2,ans3}));
}
}
|