P17210 [Template] Semi-Online Decision Monotonicity

You are given a sequence $a_1 \cdots a_n$ of length $n$ and a sequence $b_1 \cdots b_n$. Define the weight $w(l,r)$ of an interval $[l,r]$ as $$b_r+\sum\limits_{i=l}^r\sum\limits_{j=i+1}^r[a_i=a_j]$$ where $[\text{cond}] = 1$ if and only if $\text{cond}$ is true, otherwise $= 0$. For each $p = 1,2,\cdots n$, you need to partition $1 \cdots p$ into several segments so that the sum of the weights of all segments is minimized. Formally, you need to find some indices $x_0 \cdots x_k$ such that: - $x_1 = 0, x_k = p$. - $\forall i = 0,1,\cdots k-1, x_i < x_{i+1}$. Based on this, minimize $\sum\limits_{i=1}^{k} w(x_{i-1}+1,x_i)$.

The first line contains an integer $n$, representing the length of the sequences. The second line contains $n$ integers describing the sequence $a_1 \cdots a_n$ of length $n$. The third line contains $n$ integers describing the sequence $b_1 \cdots b_n$ of length $n$.

Output one line with $n$ integers, where the $i$-th integer is the answer for the prefix $1 \cdots i$.

# Constraints - For $20\%$ of the testdata, $n \leq 5000$. - For $50\%$ of the testdata, $n \leq 10^5$. - For $100\%$ of the testdata, $n \leq 5\times 10^5, 1 \leq a_i \leq n, 0 \leq b_i \leq 10^9$. Translated by ChatGPT 5