P17210 【模板】半在线决策单调性

给定一个长度为 $n$ 的序列 $a_1\cdots a_n$ 以及一个序列 $b_1\cdots b_n$。 定义一个区间 $[l,r]$ 的权值 $w(l,r)$ 为 $$b_r+\sum\limits_{i=l}^r\sum\limits_{j=i+1}^r[a_i=a_j]$$ 其中 $[\text{cond}]$ 当且仅当 $\text{cond}$ 为真时 $=1$ 否则 $=0$。 对于每一个 $p=1,2\cdots n$，请你将 $1\cdots p$ 划分成若干段，使得每段的权值之和最小，形式化的，你要找出若干下标 $x_0\cdots x_k$，使得： - $x_1=0,x_k=p$ - $\forall i=0,1,\cdots k-1,x_i

第一行一个整数 $n$ 代表序列长度。 第二行 $n$ 个整数描述一个长度为 $n$ 的序列 $a_1\cdots a_n$。 第三行 $n$ 个整数描述一个长度为 $n$ 的序列 $b_1\cdots b_n$。

一行 $n$ 个整数依次代表每一个前缀的答案。

- 对于 $20\%$ 的数据，$n\leq 5000$。 - 对于 $50\%$ 的数据，$n\leq 10^5$。 - 对于 $100\%$ 的数据，$n\leq 5\times 10^5,1\leq a_i\leq n,0\leq b_i\leq 10^9$。