Approach

Naive implementation will cost \(\Omega(N^2)\) time at worst, leading to a TLE (Time Limit Exceeded) verdict.

There are often consecutive intervals with a common left or right end, so we will try to treat them at once to optimize the algorithm.

We divide the \(N\) intervals into groups \([l_1, r_1], \dots, [l_{k}, r_{k}]\) and manage them as a list of integer tuples \((l, r, g, x)\) such that:

• all intervals with index between \(l\) and \(r\) satisfies:
  • if \(g = -1\), the left ends are all \(x\);
  • if \(g = +1\), the right ends are all \(x\).

Initially, the list solely contains \((1, N, -1, 0)\).

Queries \(1\) and \(2\)

Query \(1\) can be handled by the following procedure. Let \(i_{q}\) be the parameter of the query.

1. Repeat the following.
   • If the initial element of the list satisfies \(i_q \leq r_0\), compute \(X_L\) by the following steps.
     • If \(g_0 = -1\), let \(X_{L} = x_0\) (because the left end of interval \(i_q\) is at coordinate \(x_0\)).
     • If \(g_0 = +1\), let \(X_L = x_0 - W_{i_q}\) (because the right end of interval \(i_q\) is at coordinate \(x_0\)).
   • If the initial element of the list satisfies \(i_q < r_0\), replace \(l_0\) of the initial element with \(i_q + 1\), and terminate the loop.
   • If the initial element of the list satisfies \(i_q = r_0\), remove the initial element and terminate the loop.
   • If the initial element of the list satisfies \(i_q > r_0\), remove the initial element and terminate the loop.
2. Insert \((1, i_q, -1, X_L)\) as the initial element of the list.

Query \(2\) can be processed in the same way.

The worst complexity of this implementation is \(\Omega(N)\) per query at worst, which seems slow at a glance. However, if we track the number of elements in the list, we find the following facts:

• The list initially has \(1\) elements.
• For each query, in step 1., every iteration except for the last reduces the number of elements in the list by \(1\).
• For each query, in step 1., the last iteration reduces the number of elements by \(0\) or more.
• For each query, in step 2., the number of elements increases by \(1\).

After \(Q\) queries are finished, the increment on the element count (including the initial one) is at most \(Q+1\). Since the list cannot have less tan \(0\) elements, the iteration loops at most \((2+1)\) times at most. Therefore, the worst complexity over all \(Q\) queries is \(O(Q)\), which is fast enough.

Query \(3\)

Query \(3\) does not modify the list, so it does not affect to the complexity estimation above.

Taking a closer look at the intervals, we notice that interval \(i\) is contained in interval \((i+1)\), for \(i = 1, \dots, N-1\). Thus, there exists \(k\) such that:

• intervals \(1, \dots, k\) does not contain coordinate \(x+\frac{1}{2}\);
• intervals \(k+1, \dots, N\) contains coordinate \(x+\frac{1}{2}\).

This monotonicity allows us to find \(k\) with a binary search; then the answer is found as \(N-k\).

When you perform a binary search on the list above, you can first perform a binary search for intervals \(r_i\) to find the range \([l_i, r_i]\) that contains the smallest interval \(r_i\) containing coordinates \(x + \frac{1}{2}\); then we again perform a binary search within that range. The time complexity is \(O(\log N)\), which is fast enough.

Sample code (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;
}