動的二次元 Binary Indexed Tree を使うことで \(O(N (\log N)^2 + Q(\log N)^2)\) で解くことができます。

考え方

点 \((i, A_i)\) \((1 \leq i \leq N)\) を二次元平面にプロットすると、操作は以下のように考えることができます。

• \(t_i = 1\) のとき、ある \(y\) 軸に平行な線で区切り、それより左の領域は \(s_i\) 番のもの、右の領域は \(i\) 番のものとする。

• \(t_i = 2\) のとき、ある \(x\) 軸に平行な線で区切り、それより下の領域は \(s_i\) 番のもの、上の領域は \(i\) 番のものとする。

\(i\) 番の数列の長さは \(i\) 番の領域内にある点の個数となります。領域は長方形であり、 \(i\) 番の領域は \(l_i \leq x < r_i, d_i \leq y < u_i \) で表し、これらの値を管理すればよいです。

使用するデータ構造

長方形領域内の総和を答えるクエリに対して便利なデータ構造として、 二次元 Binary Indexed Tree などがあります。しかし、このままでは \(x\), \(y\) 座標がともに\(N\) 通りであり、計算量が \(O(N^2)\) となってしまいます。

そこで、動的二次元 Binary Indexed Tree を使用することで、 \(N\) 個の必要な箇所だけを用意してくれます。

BIT の構築と \(N\) 個の点のプロットには \(O(N (\log N)^2)\) かかります。

各操作の計算量は以下のようになります。

• \(t_i = 1\) のとき、BIT上の二分探索を利用することで \(O((\log N)^2)\) 。

• \(t_i = 2\) のとき、 \(O(1)\) 。

また、各操作後の数列の長さを求めるのは、\(O((\log N)^2)\) です。

したがって、この解法全体では、\(O(N (\log N)^2 + Q(\log N)^2)\) となり、間に合います。

下記の実装例ではBIT上の二分探索をせずに \(O(N (\log N)^2 + Q(\log N)^3)\) となっているのですが 4456 ms で間に合いました。

実装例 (C++)

動的二次元BITはnyaanさんのものを使用させていただきました。 https://nyaannyaan.github.io/library/data-structure-2d/dynamic-binary-indexed-tree-2d.hpp