<div id="readability-page-1" class="page">모든 점들을 정렬합시다. $i$번째 사람과 $j(&gt; i)$번째 사람은 최소한 $(j-i)D$ 이상 떨어져 있어야 합니다. 따라서 두 사람은 최대 $((j-i)D-(P_j-P_i))/2$ 만큼 이동해야 합니다. 그러므로 $((j-i)D-(P_j-P_i))/2$의 최댓값은 정답의 상한입니다.$t$초 이후에는 두 사람의 거리가 최대 $2t$ 만큼 변할 수 있습니다. 따라서 정답 $T$는 모든 $i &lt; j$에 대해 $P_j-P_i+2T \geq (j-i)D$를 만족해야 합니다. 식을 정리하면 $T \geq ((j-i)D-(P_j-P_i))/2$가 되므로 정답의 하한도 구했습니다.상한과 하한이 같으므로 단순히 $((j-i)D-(P_j-P_i))/2$의 최댓값을 $O(M(N+M)^2)$ 시간에 구해서 출력하면 됩니다.함수 $f(i, j) = (j-i)D-(P_j-P_i)$를 정의합시다. $O(N^2)$개의 쌍을 모두 보지 않고 $f$의 최댓값을 구해야 합니다. 
식을 정리하면 $f(i, j) = (jD-P_j) + (P_i-iD)$를 얻을 수 있고, 이때 $i$를 고정하면 $f(i, \ast)$의 최댓값은 suffix maximum을 이용해 구할 수 있습니다. 따라서 $O(N \log N + NM)$에 해결할 수 있습니다.아래 코드는 매번 <code>std::sort</code>를 호출하기 때문에 $O(NM \log N)$이지만, 새로 들어온 사람만 적절한 위치에 삽입하면 $O(N \log N + NM)$이 됩니다.맨 뒤에 새로운 값이 추가되기 때문에 suffix maximum을 전처리할 수 없습니다. 하지만 $j$를 고정한 다음 $f(\ast, j)$의 최댓값을 구하는 방식으로 접근하면 $P_i-iD$의 prefix maximum을 구하는 것이므로 동일한 방법으로 해결할 수 있습니다. 
원소를 중간에 삽입하거나 정렬할 필요가 없기 때문에 시간 복잡도는 $O(M)$입니다.새로운 수가 추가되었을 때 함수 $f(i, j) = (j-i)D-(P_j-P_i)$가 어떻게 변화하는지 살펴봅시다. 
$f(i, j) = (jD-P_j)+(P_i-iD) = (jD-P_j)-(iD-P_i)$의 최댓값을 구하는 것이 목표입니다. 어떤 위치 $x$에 수를 삽입하면 $x$보다 오른쪽에 있는 원소들의 $iD-P_i$ 값이 $D$씩 증가합니다. 
기존에 있던 원소들 간의 $f$ 값은 이미 계산되어 있으므로, 새로 $x$에 삽입한 원소들에 의해 바뀐 $f$값, 즉 ($x$의 오른쪽에서의 최댓값) - ($x$의 왼쪽에서의 최솟값)을 구해서 정답에 반영해야 합니다.$x$보다 오른쪽에 있는 원소들의 값을 $D$씩 증가시키는 연산, 구간의 최댓값과 최솟값을 찾는 연산은 좌표 압축을 수행한 뒤 세그먼트 트리를 이용해 처리할 수 있습니다.전체 시간 복잡도는 $O((N+M) \log (N+M))$입니다.<div><table><tbody><tr><td><pre>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</pre></td><td><pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;
using PLL = pair&lt;ll, ll&gt;;
constexpr int SZ = 1 &lt;&lt; 18;

PLL T[SZ&lt;&lt;1]; ll L[SZ&lt;&lt;1];
const PLL O(0x3f3f3f3f3f3f3f3f, 0xc0c0c0c0c0c0c0c0);
PLL Merge(const PLL &amp;a, const PLL &amp;b){
 return make_pair(min(a.first,b.first), max(a.second,b.second));
}
void Push(int node, int s, int e){
 T[node].first += L[node];
 T[node].second += L[node];
 if(s != e) L[node&lt;&lt;1] += L[node], L[node&lt;&lt;1|1] += L[node];
 L[node] = 0;
}
void Update(int l, int r, ll v, int node=1, int s=0, int e=SZ-1){
 Push(node, s, e);
 if(r &lt; s || e &lt; l) return;
 if(l &lt;= s &amp;&amp; e &lt;= r){ L[node] += v; Push(node, s, e); return; }
 int m = (s + e) / 2;
 Update(l, r, v, node&lt;&lt;1, s, m);
 Update(l, r, v, node&lt;&lt;1|1, m+1, e);
 T[node] = Merge(T[node&lt;&lt;1], T[node&lt;&lt;1|1]);
}
void Set(int x, ll v, int node=1, int s=0, int e=SZ-1){
 Push(node, s, e);
 if(s == e){ T[node] = {v, v}; return; }
 int m = (s + e) / 2;
 if(x &lt;= m) Set(x, v, node&lt;&lt;1, s, m), Push(node&lt;&lt;1|1, m+1, e);
 else Set(x, v, node&lt;&lt;1|1, m+1, e), Push(node&lt;&lt;1, s, m);
 T[node] = Merge(T[node&lt;&lt;1], T[node&lt;&lt;1|1]);
}
PLL Query(int l, int r, int node=1, int s=0, int e=SZ-1){
 Push(node, s, e);
 if(r &lt; s || e &lt; l) return O;
 if(l &lt;= s &amp;&amp; e &lt;= r) return T[node];
 int m = (s + e) / 2;
 return Merge(Query(l, r, node&lt;&lt;1, s, m), Query(l, r, node&lt;&lt;1|1, m+1, e));
}

ll N, M, D, P[202020], F[202020];
vector&lt;pair&lt;ll,ll&gt;&gt; C;

void Add(int x){ for(x+=3; x&lt;202020; x+=x&amp;-x) F[x]++; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&amp;-x) ret += F[x]; return ret; }

int main(){
 ios_base::sync_with_stdio(false); cin.tie(nullptr);
 cin &gt;&gt; N &gt;&gt; M &gt;&gt; D; C.reserve(N+M);
 for(int i=1; i&lt;=N+M; i++) cin &gt;&gt; P[i], C.emplace_back(P[i], i);
 sort(C.begin(), C.end());

 ll res = 0;
 fill(T, T+SZ*2, O);
 for(int q=1; q&lt;=N+M; q++){
 int pos = lower_bound(C.begin(), C.end(), make_pair(P[q], (ll)q)) - C.begin();
 int idx = Get(pos); Add(pos);
 Set(pos, idx * D - P[q]);
 Update(pos+1, C.size()-1, D);
 res = max(res, Query(pos, C.size()-1).second - Query(0, pos).first);
 if(q &gt; N) cout &lt;&lt; res / 2 &lt;&lt; (res % 2 ? ".5" : "") &lt;&lt; " \n"[q==N+M];
 }
}
</code></pre></td></tr></tbody></table></div></div>

JusticeHui가 PS하는 블로그

문제 링크
http://icpc.me/25412
문제 출처
2022 CEOI Day2 2번
사용 알고리즘
세그먼트 트리
시간복잡도
$O((N+M) \log (N+M))$
풀이
Subtask 1. $N \leq 2\,000, M \leq 10$ (10점)
모든 점들을 정렬합시다. $i$번째 사람과 $j(> i)$번째 사람은 최소한 $(j-i)D$ 이상 떨어져 있어야 합니다. 따라서 두 사람은 최대 $((j-i)D-(P_j-P_i))/2$ 만큼 이동해야 합니다. 그러므로 $((j-i)D-(P_j-P_i))/2$의 최댓값은 정답의 상한입니다.
$t$초 이후에는 두 사람의 거리가 최대 $2t$ 만큼 변할 수 있습니다. 따라서 정답 $T$는 모든 $i < j$에 대해 $P_j-P_i+2T \geq (j-i)D$를 만족해야 합니다. 식을 정리하면 $T \geq ((j-i)D-(P_j-P_i))/2$가 되므로 정답의 하한도 구했습니다.
상한과 하한이 같으므로 단순히 $((j-i)D-(P_j-P_i))/2$의 최댓값을 $O(M(N+M)^2)$ 시간에 구해서 출력하면 됩니다.
Subtask 2. $N \leq 200\,000, M \leq 10$ (24점)
함수 $f(i, j) = (j-i)D-(P_j-P_i)$를 정의합시다. $O(N^2)$개의 쌍을 모두 보지 않고 $f$의 최댓값을 구해야 합니다.
아래 코드는 매번 std::sort를 호출하기 때문에 $O(NM \log N)$이지만, 새로 들어온 사람만 적절한 위치에 삽입하면 $O(N \log N + NM)$이 됩니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, M, D;
vector<ll> V;
int main(){
 ios_base::sync_with_stdio(false); cin.tie(nullptr);
 cin >> N >> M >> D; V.resize(N);
 for(auto &i : V) cin >> i;
 for(int iter=1; iter<=M; iter++){
 int t; cin >> t; V.push_back(t);
 sort(V.begin(), V.end());
 ll res = 0, sz = V.size();
 vector<ll> mx(sz);
 for(int i=0; i<sz; i++) mx[i] = i * D - V[i];
 for(int i=sz-2; i>=0; i--) mx[i] = max(mx[i], mx[i+1]);
 for(int i=0; i<sz; i++) res = max(res, mx[i] + V[i] - i * D);
 cout << res/2 << (res % 2 ? ".5" : "") << " \n"[iter==M];
 }
}
Subtask 3. $N = 0, M \leq 200\,000, b_i \leq b_{i+1}$ (59점)
맨 뒤에 새로운 값이 추가되기 때문에 suffix maximum을 전처리할 수 없습니다. 하지만 $j$를 고정한 다음 $f(\ast, j)$의 최댓값을 구하는 방식으로 접근하면 $P_i-iD$의 prefix maximum을 구하는 것이므로 동일한 방법으로 해결할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, M, D;
vector<ll> V;
int main(){
 ios_base::sync_with_stdio(false); cin.tie(nullptr);
 cin >> N >> M >> D; V.resize(N);
 for(auto &i : V) cin >> i;
 ll res = 0; vector<ll> prefix;
 for(int iter=1; iter<=M; iter++){
 int t; cin >> t;
 if(M <= 10){
 V.push_back(t); sort(V.begin(), V.end());
 ll sz = V.size(); res = 0;
 vector<ll> mx(sz);
 for(int i=0; i<sz; i++) mx[i] = i * D - V[i];
 for(int i=sz-2; i>=0; i--) mx[i] = max(mx[i], mx[i+1]);
 for(int i=0; i<sz; i++) res = max(res, mx[i] + V[i] - i * D);
 }
 else{
 prefix.push_back(t - iter*D);
 if(prefix.size() >= 2) prefix.back() = max(prefix.back(), prefix[prefix.size()-2]);
 res = max(res, iter*D - t + prefix.back());
 }
 cout << res/2 << (res % 2 ? ".5" : "") << " \n"[iter==M];
 }
}
Subtask 4. $N = 0, M \leq 200\,000$ (100점)
새로운 수가 추가되었을 때 함수 $f(i, j) = (j-i)D-(P_j-P_i)$가 어떻게 변화하는지 살펴봅시다.
$x$보다 오른쪽에 있는 원소들의 값을 $D$씩 증가시키는 연산, 구간의 최댓값과 최솟값을 찾는 연산은 좌표 압축을 수행한 뒤 세그먼트 트리를 이용해 처리할 수 있습니다.
전체 시간 복잡도는 $O((N+M) \log (N+M))$입니다.
전체 코드
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PLL = pair<ll, ll>;
constexpr int SZ = 1 << 18;
PLL T[SZ<<1]; ll L[SZ<<1];
const PLL O(0x3f3f3f3f3f3f3f3f, 0xc0c0c0c0c0c0c0c0);
PLL Merge(const PLL &a, const PLL &b){
 return make_pair(min(a.first,b.first), max(a.second,b.second));
}
void Push(int node, int s, int e){
 T[node].first += L[node];
 T[node].second += L[node];
 if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
 L[node] = 0;
}
void Update(int l, int r, ll v, int node=1, int s=0, int e=SZ-1){
 Push(node, s, e);
 if(r < s || e < l) return;
 if(l <= s && e <= r){ L[node] += v; Push(node, s, e); return; }
 int m = (s + e) / 2;
 Update(l, r, v, node<<1, s, m);
 Update(l, r, v, node<<1|1, m+1, e);
 T[node] = Merge(T[node<<1], T[node<<1|1]);
}
void Set(int x, ll v, int node=1, int s=0, int e=SZ-1){
 Push(node, s, e);
 if(s == e){ T[node] = {v, v}; return; }
 int m = (s + e) / 2;
 if(x <= m) Set(x, v, node<<1, s, m), Push(node<<1|1, m+1, e);
 else Set(x, v, node<<1|1, m+1, e), Push(node<<1, s, m);
 T[node] = Merge(T[node<<1], T[node<<1|1]);
}
PLL Query(int l, int r, int node=1, int s=0, int e=SZ-1){
 Push(node, s, e);
 if(r < s || e < l) return O;
 if(l <= s && e <= r) return T[node];
 int m = (s + e) / 2;
 return Merge(Query(l, r, node<<1, s, m), Query(l, r, node<<1|1, m+1, e));
}
ll N, M, D, P[202020], F[202020];
vector<pair<ll,ll>> C;
void Add(int x){ for(x+=3; x<202020; x+=x&-x) F[x]++; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&-x) ret += F[x]; return ret; }
int main(){
 ios_base::sync_with_stdio(false); cin.tie(nullptr);
 cin >> N >> M >> D; C.reserve(N+M);
 for(int i=1; i<=N+M; i++) cin >> P[i], C.emplace_back(P[i], i);
 sort(C.begin(), C.end());
 ll res = 0;
 fill(T, T+SZ*2, O);
 for(int q=1; q<=N+M; q++){
 int pos = lower_bound(C.begin(), C.end(), make_pair(P[q], (ll)q)) - C.begin();
 int idx = Get(pos); Add(pos);
 Set(pos, idx * D - P[q]);
 Update(pos+1, C.size()-1, D);
 res = max(res, Query(pos, C.size()-1).second - Query(0, pos).first);
 if(q > N) cout << res / 2 << (res % 2 ? ".5" : "") << " \n"[q==N+M];
 }
}

백준25412 Measures

댓글