実装方針

素朴に実装すると最悪ケースで \(\Omega(N^2)\) 時間かかり，実行時間超過となります．

連続して左端が揃っている範囲や，連続して右端が揃っている範囲をまとめて管理することで高速化することを考えます．

\(N\) 個の区間を範囲 \([l_1, r_1], \dots, [l_{k}, r_{k}]\) に分割し，以下の条件を表す整数組 \((l, r, g, x)\) のリストとして管理します．

• 番号が \(l\) 以上 \(r\) 以下の区間は，まとめて以下を満たす．
  • \(g = -1\) の場合，左端が座標 \(x\) で揃っている．
  • \(g = +1\) の場合，右端が座標 \(x\) で揃っている．

リストの初期値は \((1, N, -1, 0)\) のみの \(1\) 要素とします．

クエリ \(1, 2\)

クエリ \(1\) は以下のように実現できます．クエリで与えられる値を \(i_{q}\) とします．

1. 以下の操作を繰り返す．
   • リストの先頭要素が \(i_q \leq r_0\) を満たす場合，以下にしたがって変数 \(X_L\) の値を得る．
     • \(g_0 = -1\) ならば \(X_{L} = x_0\) とする(区間 \(i_q\) の左端が座標 \(x_0\) にあるため)．
     • \(g_0 = +1\) ならば \(X_L = x_0 - W_{i_q}\) とする(区間 \(i_q\) の右端が座標 \(x_0\) にあるため)．
   • リストの先頭要素が \(i_q < r_0\) を満たす場合，先頭要素の \(l_0\) を \(i_q + 1\) で置き換えてループを終える．
   • リストの先頭要素が \(i_q = r_0\) を満たす場合，先頭要素を削除してループを終える．
   • リストの先頭要素が \(i_q > r_0\) を満たす場合，先頭要素を削除してループを続行する．
2. リストの先頭に \((1, i_q, -1, X_L)\) を追加する．

クエリ \(2\) も同様にして実現できます．

この実装のクエリ \(1\) つあたりの最悪計算量は \(\Omega(N)\) であり，一見して遅いように見えます．ですが，リストの要素数に注目すると，以下の事実が分かります．

• リストの要素数ははじめ \(1\)．
• 各クエリの操作 1. において，最後でない反復 \(1\) 回ごとにリストの要素数は \(1\) 減少する．
• 各クエリの操作 1. において，最後の反復でリストの要素数は \(0\) 以上減少する．
• 各クエリの操作 2. において，リストの要素数は \(1\) 増加する．

\(Q\) 回のクエリが終わった時点で，リストの要素数の増加量 (初期値のぶん含む) は高々 \(Q+1\) です．リストの要素数は \(0\) を下回らないので，反復の回数は高々 \(2Q+1\) 回で抑えられることが分かります． したがって，\(Q\) 個のクエリ全体にわたっての最悪計算量は \(O(Q)\) になっており，高速です．

クエリ \(3\)

クエリ \(3\) において，リストは変更しないので，上の計算量評価に影響はありません．

区間のようすを観察すると，\(i = 1, \dots, N-1\) で，区間 \(i\) は区間 \(i+1\) に含まれることが分かります．したがって，以下を満たす \(k\) が存在します．

• 区間 \(1, \dots, k\) は座標 \(x+\frac{1}{2}\) を含まない．
• 区間 \(k+1, \dots, N\) は座標 \(x+\frac{1}{2}\) を含む．

この単調性より，二分探索によって \(k\) を求めれば，\(N-k\) が答えとなります．

上のリストに対して二分探索を行う場合は，まず各要素に対して区間 \(r_i\) を代表として二分探索を行い，座標 \(x + \frac{1}{2}\) を含む最小の区間 \(r_i\) をもつ範囲 \([l_i, r_i]\) に対して再度二分探索を行えばよいです．時間計算量は \(O(\log N)\) となり，十分高速です．

実装例 (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::min;
using std::max;
#include <vector>
using std::vector;

typedef long long int ll;

ll n, q;
vector<ll> w;

typedef struct {
	ll li;
	ll ri;
	ll gravity;
	ll x;
} Block;
vector<Block> bar;

void barclear (ll v, ll dir) {
	while (true) {
		Block b = bar.back();
		bar.pop_back();

		if (b.ri >= v) {
			if (v+1 <= b.ri) {
				bar.push_back({v+1, b.ri, b.gravity, b.x});
			}
			ll fl, fr;
			if (b.gravity < 0) {
				fl = b.x;
				fr = fl + w[v];
			} else {
				fr = b.x;
				fl = fr - w[v];
			}
			ll currx = ((dir < 0) ? fl : fr);
			bar.push_back({0, v, dir, currx});
			break;
		}
	}
}

int main (void) {
	cin >> n;
	w.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> w[i];
	}

	// init
	bar.push_back({0, n-1, -1, 0});

	cin >> q;
	for (ll qi = 0; qi < q; qi++) {
		ll type;
		cin >> type;
		if (type == 1) {
			ll v;
			cin >> v;
			--v;
			// type 1
			barclear(v, -1);
		} else if (type == 2) {
			ll v;
			cin >> v;
			--v;
			// type 2
			barclear(v, +1);
		} else if (type == 3) {
			ll x;
			cin >> x;
			// type 3
			ll ans;
			ll idx;
			{
				ll ok = -1, ng = bar.size();
				while (ok + 1 < ng) {
					ll med = (ok + ng) / 2;
					ll fl, fr;
					if (bar[med].gravity < 0) {
						fl = bar[med].x;
						fr = fl + w[bar[med].ri];
					} else {
						fr = bar[med].x;
						fl = fr - w[bar[med].ri];
					}
					if (fl <= x && x < fr) {
						ok = med;
					} else {
						ng = med;
					}
				}
				idx = ok;
			}
			if (idx < 0) {
				ans = 0;
			} else {
				ll fl, fr;
				ll ok = bar[idx].ri, ng = bar[idx].li - 1;
				while (ng + 1 < ok) {
					ll med = (ok + ng) / 2;
					if (bar[idx].gravity < 0) {
						fl = bar[idx].x;
						fr = fl + w[med];
					} else {
						fr = bar[idx].x;
						fl = fr - w[med];
					}
					if (fl <= x && x < fr) {
						ok = med;
					} else {
						ng = med;
					}
				}
				ans = n - ok;
			}

			cout << ans << "\n";
		}

	}
	
	return 0;
}