求助数据结构问题

自己想的一道数据结构，题目如下：

给定正整数 $n$ 和一个关于 $1\sim n$ 的排列 $b_1,b_2,..., b _ n$。

要求维护一个数列 $a_1,a_2,...,a_n$，初值全为 $0$，有两种操作：

其中 $1\le n,m\le 10^5$，$m$ 是操作数，保证任何时刻的 $a_i$ 的绝对值不超过 $1000$。

在 $\{b_n\}$ 随机生成时，存在 $O(n\log ^2n)$ 的做法。但是在刻意构造下会变成 $O(n^2\log n)$，因此想问问有没有更好的解法。