Bombs

Let's come up with some criteria that answer is <x.

We claim that the answer is <x if:

There is at least one bomb after the rightmost value ≥x.
There are at least two bombs after the next rightmost value ≥x.
...

There are at least k bombs after the k-th rightmost value ≥x.
Let ansi be the answer for bombs q1,q2,…,qi−1.

Then, ansi≥ansi+1.

Let's add new bombs starting from ansi−1, and while the actual answer is smaller than the current answer, decrease the actual answer.

To do this quickly, we'll use a segment tree.

In the segment tree, let's store bi= (number of values ≥x on suffix i…n) − (number of bombs on this suffix).

Then, the real answer is <x if bi≤0 for all i.

Using range addition updates and max queries, we can update b and decrease the answer quickly.

#include <bits/stdc++.h>
using namespace std;

const int MX = 3e5 + 1;

int st[4 * MX], la[4 * MX], p[MX], q[MX], pos[MX], n;

void push(int v) {
	st[v * 2] += la[v];
	la[v * 2] += la[v];
	st[v * 2 + 1] += la[v];
	la[v * 2 + 1] += la[v];
	la[v] = 0;
}

void upd(int a, int b, int val, int v = 1, int l = 1, int r = n) {
	if (b < l || r < a)
		return;
	if (a <= l && r <= b) {
		st[v] += val;
		la[v] += val;
	} else {
		push(v);
		int m = (l + r) / 2;
		upd(a, b, val, v * 2, l, m);
		upd(a, b, val, v * 2 + 1, m + 1, r);
		st[v] = max(st[v * 2], st[v * 2 + 1]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> p[i];
		pos[p[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		cin >> q[i];
	}

	int cur = n;
	upd(1, pos[n], 1);
	for (int i = 1; i <= n; ++i) {
		cout << cur << ' ';
		upd(1, q[i], -1);
		while (cur && st[1] <= 0) {
			upd(1, pos[--cur], 1);
		}
	}
	cout << '\n';
}


/**
 * Description: 1D range update and query. Set SZ to a power of 2.
 * Source: USACO Counting Haybales
 * Verification: SPOJ Horrible
 */

template<class T, int SZ> struct LazySeg {
	T mx[2*SZ], lazy[2*SZ];
	LazySeg() { F0R(i,2*SZ) mx[i] = lazy[i] = 0; }
	void push(int ind, int L, int R) { /// modify values for current node
		if (L != R) F0R(i,2) lazy[2*ind+i] += lazy[ind]; /// prop to children
		mx[ind] += lazy[ind]; lazy[ind] = 0;
	} // recalc values for current node
	void pull(int ind) { mx[ind] = max(mx[2*ind],mx[2*ind+1]); }
	void build() { ROF(i,1,SZ) pull(i); }
	void upd(int lo,int hi,T inc,int ind=1,int L=0, int R=SZ-1) {
		push(ind,L,R); if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) {
			lazy[ind] = inc; push(ind,L,R); return; }
		int M = (L+R)/2;
		upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
		pull(ind);
	}
	int firstGre(int ind = 1, int L = 0, int R = SZ-1) {
		push(ind,L,R); assert(mx[ind] > 0);
		if (L == R) return L;
		int M = (L+R)/2;
		push(2*ind,L,M);
		if (mx[2*ind] > 0) return firstGre(2*ind,L,M);
		return firstGre(2*ind+1,M+1,R);
	}
};
LazySeg<ll,1<<19> L;

/**
 * Description: 1D point update, range query where \texttt{comb} is
 	* any associative operation. If $N$ is not power of 2 then
 	* operations work but \texttt{seg[1] != query(0,N-1)}.
 * Time: O(\log N)
 * Source:
	* http://codeforces.com/blog/entry/18051
	* KACTL
 * Verification: SPOJ Fenwick
 */

template<class T> struct Seg { // comb(ID,b) = b
	const T ID = 0; T comb(T a, T b) { return max(a,b); }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// sum on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};
Seg<int> S;

int n,rp[MX];
vi p,q;

int getMax(int r) {
	int t = S.query(1,r); assert(t);
	return rp[t];
}

int main() {
	setIO();
	re(n);
	p.rsz(n); re(p);
	q.rsz(n); re(q);
	S.init(1<<19);
	F0R(i,n) {
		S.upd(i+1,p[i]);
		rp[p[i]] = i+1;
	}
	L.upd(1,n,-MOD);
	trav(t,q) { // query max over range
		pr(S.query(1,n),' ');
		L.upd(t,t,MOD);
		L.upd(t,n,1);
		int x = L.firstGre();
		int z = getMax(x);
		L.upd(z,n,-1); S.upd(z,0);
	} //
	// you should actually read the stuff at the bottom
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/