Ex - Monster Editorial by en_translator
1. Limit the segments to construct binary-tree structure
First of all, since the order of Takahashi’s magic does not affect to the change of stamina and MP (Magic Point), what only matters is how many times each segment is chosen. Moreover, it is always better to chose wider range as long as the required MP does not change. That is, it is sufficient to choose \((l, r)\) satisfying \(1\leq r\leq N\) such that
- \(B_{l-1}>B_j\) or \(l=1\) for all \(j\) such that \(l\leq j\leq r\); and
- \(B_{r+1}>B_j\) or \(r=N\) for all \(j\) such that \(l\leq j\leq r\).
Such a segment can be represented by \((l_i,r_i)\) defined by corresponding it to \(i\) that maximizes \(B_i\) (with ties broken by choosing the largest \(i\); same applies when taking such \(i\) afterwards), i.e. \((l_i,r_i)\) is specifically defined as follows:
- \(l_i=j+1\) for the maximum \(j\) such that \(j<i\) and \(B_j>B_i\), or \(l_i=1\) if there is no such \(j\);
- \(r_i=j-1\) for the maximum \(j\) such that \(j>i\) and \(B_j \geq B_i\), or \(r_i=N\) if there is no such \(j\).
Therefore, we only need to consider performing operations on these segments. (There may be excessive segments, but it doesn’t matter if we just don’t use it.)
Here, we can consider the following binary-tree structure rooted at vertex \(i\) such that \(B_i\) is the maximum in \(B_1,\ldots,B_N\) (note that \((l_R,r_R)=(1,N)\) for the root \(R\)):
- the (direct) left child of vertex \(i\) is \(j\) satisfying \(l_i\leq j\leq i-1\) that maximizes \(B_j\) if \(l_i< i\); otherwise vertex \(i\) does not have a left child;
- the (direct) right child of vertex \(i\) is \(j\) satisfying \(i+1\leq j\leq r_i\) that maximizes \(B_j\) if \(i<r_i\); otherwise vertex \(i\) does not have a right child.
Then, for vertex \(i\),
- if vertex \(i\) has a left child \(x\), then \((l_x,r_x)=(l_i,i-1)\);
- if vertex \(i\) has a right child \(y\), then \((l_y,r_y)=(i+1,r_i)\).
2. Setup and update of DP (Dynamic Programming)
Let us define \(dp[i][j]\) by the answer (minimum sum of MP required) when \(N'=r_i-l_i+1\), \(A'=(A_{l_i}-j,A_{l_i+1}-j,\ldots,A_{r_i}-j)\), \(B'=(B_{l_i},B_{l_i+1}, \ldots,B_{r_i})\).
What we want is \(dp[R][0]\).
Consider finding them for all \(i\) in ascending order of \(B_i\).
At the same time, we will show by induction that \(dp[i][j]\) is monotonically decreasing with respect to \(j\), and so is \((dp[i][j]-dp[i][j+1]\)).
First, if \(l_i=r_i=i\),
\[ dp[i][j]= \begin{cases} (A_i-j)B_i & (0\leq j\leq A_i) \\ 0 & (A_i\leq j), \end{cases} \]
which satisfies the assumption.
Otherwise, suppose vertex \(i\) has left child and \(x\) and right child \(y\). Notice here that, by the definition of the binary tree and segments, \(B_x\leq B_i\), \(B_y<B_i\), and thus we already know \(dp[x][j]\) and \(dp[y][j]\). Also, if it has not any child, we can let \(dp[x][j](\text{or }dp[y][j])\equiv 0\) in the following discussion.
Since Takahashi need to cease the stamina of the monster at coordinate \(i\), here we have
\[ dp[i][j]=\displaystyle\min_{\max(A_i-j,0)\leq k} \{kB_i+ dp[x][j+k]+dp[y][j+k]\}. \]
When \(k\) is incremented by \(1\), \(kB_i+ dp[x][j+k]+dp[y][j+k]\) is displaced by \(B_i-(dp[x][j+k]-dp[x][j+k+1])-(dp[y][j+k]-dp[y][j+k+1])\), which is monotonically increasing by the assumption of the induction. Therefore, for some \(j_0\geq A_i\), the following two holds:
- \(j_0=A_i\) or \(B_i-(dp[x][j_0-1]-dp[x][j_0])-(dp[y][j_0-1]-dp[y][j_0])\leq 0\);
- \(B_i-(dp[x][j_0]-dp[x][j_0+1])-(dp[y][j_0]-dp[y][j_0+1])> 0\).
On one hand, if \(j\leq j_0\) here,
\[ dp[i][j]=(j_0-j)B_i+ dp[x][j_0]+dp[y][j_0], \]
and on the other hand, i.e. if \(j\geq j_0\), there is no advantage in increasing \(k\) beyond \(0\), so
\[ dp[i][j]=dp[x][j]+dp[y][j]. \]
By the assumption of the induction, \(dp[i][j]\) is monotonically decreasing, and \(B_i>(dp[x][j_0]+dp[y][j_0])-(dp[x][j_0+1]+dp[y][j_0+1])\), so \(dp[i][j]-dp[i][j+1]\) is monotonically decreasing too.
We can thus obtain the values \(dp[i][j]\) inductively.
3. Polyline optimization
Now, consider the range of indices \(j\) of \(dp[i][j]\). We have \(dp[i][j]=0\) for \(j\geq \max(A_{l_i},\ldots,A_{r_i})\), but conversely, we need to compute up to there, that is, up to about \(j\simeq 10^9\), which doesn’t finish in time. Here, notice that \(dp[i][j]\) decreases by equal amount almost everywhere; \(dp[i][j]-dp[i][j+1]\) changes at as many points as the number of vertices in the subtree rooted at the vertex. Therefore, instead of explicitly maintaining \(dp[i][j]\), consider maintaining \(dp[i][0]\), \(dp[i][0]-dp[i][1]\), and
\[ S_i=\{(j,(dp[i][j-1]-dp[i][j])-(dp[i][j]-dp[i][j+1]))| \text{for }j\text{ such that }(dp[i][j-1]-dp[i][j])\neq (dp[i][j]-dp[i][j+1])\}. \]
Then, an update consists of two steps:
Merging \(dp[x][j]\) and \(dp[y][j]\) (\(dp'\) and \(S'_i\) denote intermediate values begin computed, which are different from the final ones)
- \(dp'[i][0]=dp[x][0]+dp[y][0]\)
- \(dp'[i][0]-dp'[i][1]=(dp[x][0]-dp[x][1])+(dp[y][0]-dp[y][1])\)
- \(S'_i=S_x\bigcup S_y\)
Reflecting \((A_i, B_i)\)
- Using information we obtained in 1., compute \(dp'[i][j]\) in order, so as to find the minimum \(j=j_0\) such that \(j\geq A_i\) and \(B_i>dp'[i][j]-dp'[i][j+1](=(dp[x][j]+dp[y][j])-(dp[x][j+1]+dp[y][j+1]))\).
- \(dp[i][0]=dp'[i][j_0]+j_0B_i\)
- \(dp[i][0]-dp[i][1]=B_i\)
- Remove \((j,x)\in S'_i\) for \(j\leq j_0\).
- Add \((j_0,B_i-(dp'[i][j_0]-dp'[i][j_0+1]))\) to \(S'\).
This concludes the description of an update.
We finally consider the complexity. When merging \(S_x\) and \(S_y\), we can merge into the larger of \(S_x\) and \(S_y\) and let it \(S_i\) anew, for a total of \(O(N\log N)\) insertions into \(S_i\). Also, computing \(dp'[i][j]\) up to \(j=j_0\) costs \(O(N\log N)\) too, as every element (except for one) in \(S_i\) is removed once removed. By managing \(S_i\) in an ordered multiset or a priority queue, insertion, reference, and removal can be preformed in an \(O(\log N)\) time, so updating DP costs a total of \(O(N\log^2 N)\) time. Since finding \(l_i\) and \(r_i\) can be done with an ordered set in a total of \(O(N\log N)\) time, so the overall time complexity is \(O(N\log^2 N)\), which is fast enough to solve this problem.
Sample code in C++:
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define INF (long long)4e+18
int main() {
int n;
long long a[N];
long long b[N];
int c[N][2];
int x,y;
set<int>st;
set<int>::iterator itr;
vector<pair<long long,int> >ord;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
ord.push_back({b[i],i});
}
b[0]=INF;
b[n+1]=INF;
sort(ord.begin(),ord.end());
for(int i=1;i<=n;i++)for(int j=0;j<2;j++)c[i][j]=-1;
st.insert(0);
st.insert(n+1);
for(int i=n-1;i>=0;i--){
itr=st.upper_bound(ord[i].second);
y=(*itr);
itr--;
x=(*itr);
if(b[x]<=b[y])c[x][1]=ord[i].second;
else c[y][0]=ord[i].second;
st.insert(ord[i].second);
}
int k;
int p[N];
long long dp0[N];
long long d[N];
long long cur;
multiset<pair<long long,long long> >mst[N];
multiset<pair<long long,long long> >::iterator mstitr;
pair<long long,long long> z;
for(int i=1;i<=n;i++)p[i]=i;
for(int i=0;i<n;i++){
k=ord[i].second;
if((c[k][0]==-1)&&(c[k][1]==-1)){
dp0[k]=a[k]*b[k];
d[k]=b[k];
mst[k].insert({a[k],b[k]});
continue;
}
if(c[k][0]==-1)p[k]=p[c[k][1]];
else if(c[k][1]==-1)p[k]=p[c[k][0]];
else if(mst[p[c[k][0]]].size()<mst[p[c[k][1]]].size()){
p[k]=p[c[k][1]];
dp0[p[k]]+=dp0[p[c[k][0]]];
d[p[k]]+=d[p[c[k][0]]];
mst[p[k]].merge( mst[p[c[k][0]]]);
}
else{
p[k]=p[c[k][0]];
dp0[p[k]]+=dp0[p[c[k][1]]];
d[p[k]]+=d[p[c[k][1]]];
mst[p[k]].merge( mst[p[c[k][1]]]);
}
cur=0;
while(!mst[p[k]].empty()){
mstitr=mst[p[k]].begin();
z=(*mstitr);
if((z.first<=a[k])||(d[p[k]]>=b[k])){
dp0[p[k]]-=(z.first-cur)*d[p[k]];
d[p[k]]-=z.second;
cur=z.first;
mst[p[k]].erase(mstitr);
}
else break;
}
if(cur<a[k]){
dp0[p[k]]-=(a[k]-cur)*d[p[k]];
cur=a[k];
}
mst[p[k]].insert({cur,b[k]-d[p[k]]});
dp0[p[k]]+=(cur*b[k]);
d[p[k]]=b[k];
}
cout<<dp0[p[ord[n-1].second]]<<endl;
return 0;
}
posted:
last update: