Bombs (Codeforces 1326E)
Tags: Others, two pointers

You are given a permutation, $$$p_1, p_2, \ldots, p_n$$$.Imagine that some positions of the permutation contain bombs, such that there exists at least one position without a bomb.For some fixed configuration of bombs, consider the following process. Initially, there is an empty set, $$$A$$$.For each $$$i$$$ from $$$1$$$ to $$$n$$$: Add $$$p_i$$$ to $$$A$$$.  If the $$$i$$$-th position contains a bomb, remove the largest element in $$$A$$$.After the process is completed, $$$A$$$ will be non-empty. The cost of the configuration of bombs equals the largest element in $$$A$$$.You are given another permutation, $$$q_1, q_2, \ldots, q_n$$$.For each $$$1 \leq i \leq n$$$, find the cost of a configuration of bombs such that there exists a bomb in positions $$$q_1, q_2, \ldots, q_{i-1}$$$. For example, for $$$i=1$$$, you need to find the cost of a configuration without bombs, and for $$$i=n$$$, you need to find the cost of a configuration with bombs in positions $$$q_1, q_2, \ldots, q_{n-1}$$$.

Input: The first line contains a single integer, $$$n$$$ ($$$2 \leq n \leq 300\,000$$$).The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n)$$$.The third line contains $$$n$$$ distinct integers $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \leq q_i \leq n)$$$.

Output: Print $$$n$$$ space-separated integers, such that the $$$i$$$-th of them equals the cost of a configuration of bombs in positions $$$q_1, q_2, \ldots, q_{i-1}$$$.

Note: In the first test:  If there are no bombs, $$$A$$$ is equal to $$$\{1, 2, 3\}$$$ at the end of the process, so the cost of the configuration is $$$3$$$.  If there is one bomb in position $$$1$$$, $$$A$$$ is equal to $$$\{1, 2\}$$$ at the end of the process, so the cost of the configuration is $$$2$$$;  If there are two bombs in positions $$$1$$$ and $$$2$$$, $$$A$$$ is equal to $$$\{1\}$$$ at the end of the process, so the cost of the configuration is $$$1$$$. In the second test:Let's consider the process for $$$i = 4$$$. There are three bombs on positions $$$q_1 = 5$$$, $$$q_2 = 2$$$, and $$$q_3 = 1$$$.At the beginning, $$$A = \{\}$$$.  Operation $$$1$$$: Add $$$p_1 = 2$$$ to $$$A$$$, so $$$A$$$ is equal to $$$\{2\}$$$. There exists a bomb in position $$$1$$$, so we should delete the largest element from $$$A$$$. $$$A$$$ is equal to $$$\{\}$$$.  Operation $$$2$$$: Add $$$p_2 = 3$$$ to $$$A$$$, so $$$A$$$ is equal to $$$\{3\}$$$. There exists a bomb in position $$$2$$$, so we should delete the largest element from $$$A$$$. $$$A$$$ is equal to $$$\{\}$$$.  Operation $$$3$$$: Add $$$p_3 = 6$$$ to $$$A$$$, so $$$A$$$ is equal to $$$\{6\}$$$. There is no bomb in position $$$3$$$, so we do nothing.  Operation $$$4$$$: Add $$$p_4 = 1$$$ to $$$A$$$, so $$$A$$$ is equal to $$$\{1, 6\}$$$. There is no bomb in position $$$4$$$, so we do nothing.  Operation $$$5$$$: Add $$$p_5 = 5$$$ to $$$A$$$, so $$$A$$$ is equal to $$$\{1, 5, 6\}$$$. There exists a bomb in position $$$5$$$, so we delete the largest element from $$$A$$$. Now, $$$A$$$ is equal to $$$\{1, 5\}$$$.  Operation $$$6$$$: Add $$$p_6 = 4$$$ to $$$A$$$, so $$$A$$$ is equal to $$$\{1, 4, 5\}$$$. There is no bomb in position $$$6$$$, so we do nothing. In the end, we have $$$A = \{1, 4, 5\}$$$, so the cost of the configuration is equal to $$$5$$$.

Sample Inputs:
3
3 2 1
1 2 3

6
2 3 6 1 5 4
5 2 1 4 6 3

Sample Outputs:
3 2 1

6 5 5 5 4 1

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class LazySegmentTree:

    def __init__(self, data, default=1000000000.0, func=min):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """"""
        (q, self._lazy[idx]) = (self._lazy[idx], 0)
        self._lazy[2 * idx] += q
        self._lazy[2 * idx + 1] += q
        self.data[2 * idx] += q
        self.data[2 * idx + 1] += q

    def _update(self, idx):
        """"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """"""
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1]) + self._lazy[idx]
            idx >>= 1

    def add(self, start, stop, value):
        """"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] += value
                self.data[start] += value
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] += value
                self.data[stop] += value
            start >>= 1
            stop >>= 1
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=1000000000.0):
        """"""
        start += self._size
        stop += self._size
        self._update(start)
        self._update(stop - 1)
        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return 'LazySegmentTree({0})'.format(self.data)
n = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))
q = list(map(lambda x: int(x) - 1, input().split()))
tree = LazySegmentTree([0] * n)
ans = []

def decrease(x):
    tree.add(0, ref[x] + 1, -1)
    if tree.query(0, ref[x] + 1) >= 0:
        return True
    else:
        tree.add(0, ref[x] + 1, 1)
        return False
x = n - 1
ref = [0] * n
for i in range(n):
    ref[p[i]] = i
for i in range(n):
    while decrease(x):
        x -= 1
    ans.append(x + 1)
    tree.add(0, q[i] + 1, 1)
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
seg_el = 1 << N.bit_length()
SEG = [0] * (2 * seg_el)
LAZY = [0] * (2 * seg_el)

def indexes(L, R):
    INDLIST = []
    R -= 1
    L >>= 1
    R >>= 1
    while L != R:
        if L > R:
            INDLIST.append(L)
            L >>= 1
        else:
            INDLIST.append(R)
            R >>= 1
    while L != 0:
        INDLIST.append(L)
        L >>= 1
    return INDLIST

def adds(l, r, x):
    L = l + seg_el
    R = r + seg_el
    L //= L & -L
    R //= R & -R
    UPIND = indexes(L, R)
    for ind in UPIND[::-1]:
        if LAZY[ind] != 0:
            plus_lazy = LAZY[ind]
            SEG[ind << 1] += plus_lazy
            SEG[1 + (ind << 1)] += plus_lazy
            LAZY[ind << 1] += plus_lazy
            LAZY[1 + (ind << 1)] += plus_lazy
            LAZY[ind] = 0
    while L != R:
        if L > R:
            SEG[L] += x
            LAZY[L] += x
            L += 1
            L //= L & -L
        else:
            R -= 1
            SEG[R] += x
            LAZY[R] += x
            R //= R & -R
    for ind in UPIND:
        SEG[ind] = min(SEG[ind << 1], SEG[1 + (ind << 1)])

def getvalues(l, r):
    L = l + seg_el
    R = r + seg_el
    L //= L & -L
    R //= R & -R
    UPIND = indexes(L, R)
    for ind in UPIND[::-1]:
        if LAZY[ind] != 0:
            plus_lazy = LAZY[ind]
            SEG[ind << 1] += plus_lazy
            SEG[1 + (ind << 1)] += plus_lazy
            LAZY[ind << 1] += plus_lazy
            LAZY[1 + (ind << 1)] += plus_lazy
            LAZY[ind] = 0
    ANS = 1 << 31
    while L != R:
        if L > R:
            ANS = min(ANS, SEG[L])
            L += 1
            L //= L & -L
        else:
            R -= 1
            ANS = min(ANS, SEG[R])
            R //= R & -R
    return ANS
from operator import itemgetter
NOW = 0
P_INV = sorted([(p, i) for (i, p) in enumerate(P)], key=itemgetter(0), reverse=True)
adds(P_INV[NOW][1], N, 1)
ANS = [NOW]
for q in Q[:-1]:
    adds(q - 1, N, -1)
    while True:
        if getvalues(0, seg_el - 1) < getvalues(N - 1, N):
            ANS.append(NOW)
            break
        else:
            NOW += 1
            adds(P_INV[NOW][1], N, 1)
print(*[N - a for a in ANS])

Solution (Python):
if True:
    from io import BytesIO, IOBase
    import math
    import random
    import sys
    import os
    import bisect
    import typing
    from collections import Counter, defaultdict, deque
    from copy import deepcopy
    from functools import cmp_to_key, lru_cache, reduce
    from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
    from itertools import accumulate, combinations, permutations, count
    from operator import add, iand, ior, itemgetter, mul, xor
    from string import ascii_lowercase, ascii_uppercase, ascii_letters
    from typing import *
    BUFSIZE = 4096

    class FastIO(IOBase):
        newlines = 0

        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = 'x' in file.mode or 'r' not in file.mode
            self.write = self.buffer.write if self.writable else None

        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines = 0
            return self.buffer.read()

        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b'\n') + (not b)
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines -= 1
            return self.buffer.readline()

        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                (self.buffer.truncate(0), self.buffer.seek(0))

    class IOWrapper(IOBase):

        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda : self.buffer.read().decode('ascii')
            self.readline = lambda : self.buffer.readline().decode('ascii')
    sys.stdin = IOWrapper(sys.stdin)
    sys.stdout = IOWrapper(sys.stdout)
    input = lambda : sys.stdin.readline().rstrip('\r\n')

    def I():
        return input()

    def II():
        return int(input())

    def MII():
        return map(int, input().split())

    def LI():
        return list(input().split())

    def LII():
        return list(map(int, input().split()))

    def LFI():
        return list(map(float, input().split()))

    def GMI():
        return map(lambda x: int(x) - 1, input().split())

    def LGMI():
        return list(map(lambda x: int(x) - 1, input().split()))
    inf = float('inf')
(dfs, hashing) = (False, False)
if dfs:
    from types import GeneratorType

    def bootstrap(f, stack=[]):

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if type(to) is GeneratorType:
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc
if hashing:
    RANDOM = random.getrandbits(20)

    class Wrapper(int):

        def __init__(self, x):
            int.__init__(x)

        def __hash__(self):
            return super(Wrapper, self).__hash__() ^ RANDOM

class LazySegTree:

    def __init__(self, op: typing.Callable[[typing.Any, typing.Any], typing.Any], e: typing.Any, mapping: typing.Callable[[typing.Any, typing.Any], typing.Any], composition: typing.Callable[[typing.Any, typing.Any], typing.Any], id_: typing.Any, v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_
        if isinstance(v, int):
            v = [e] * v
        self._n = len(v)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        if left == right:
            return self._e
        left += self._size
        right += self._size
        for i in range(self._log, 0, -1):
            if left >> i << i != left:
                self._push(left >> i)
            if right >> i << i != right:
                self._push(right >> i)
        sml = self._e
        smr = self._e
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1
        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int]=None, f: typing.Optional[typing.Any]=None) -> None:
        assert f is not None
        if right is None:
            p = left
            assert 0 <= left < self._n
            p += self._size
            for i in range(self._log, 0, -1):
                self._push(p >> i)
            self._d[p] = self._mapping(f, self._d[p])
            for i in range(1, self._log + 1):
                self._update(p >> i)
        else:
            assert 0 <= left <= right <= self._n
            if left == right:
                return
            left += self._size
            right += self._size
            for i in range(self._log, 0, -1):
                if left >> i << i != left:
                    self._push(left >> i)
                if right >> i << i != right:
                    self._push(right - 1 >> i)
            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2
            for i in range(1, self._log + 1):
                if left >> i << i != left:
                    self._update(left >> i)
                if right >> i << i != right:
                    self._update(right - 1 >> i)

    def max_right(self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)
        if left == self._n:
            return self._n
        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)
        sm = self._e
        first = True
        while first or left & -left != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1
        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)
        if right == 0:
            return 0
        right += self._size
        for i in range(self._log, 0, -1):
            self._push(right - 1 >> i)
        sm = self._e
        first = True
        while first or right & -right != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)
        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> None:
        self._d[k] = self._mapping(f, self._d[k])
        if k < self._size:
            self._lz[k] = self._composition(f, self._lz[k])

    def _push(self, k: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id
n = II()
perm1 = LGMI()
pos = [None] * n
for (i, v) in enumerate(perm1):
    pos[v] = i
perm2 = LII()

def decrease():
    seg.apply(0, pos[pt] + 1, -1)
    if seg.all_prod() >= 0:
        return True
    seg.apply(0, pos[pt] + 1, 1)
    return False
pt = n - 1
seg = LazySegTree(min, inf, add, add, 0, [0] * n)
for i in range(n):
    while decrease():
        pt -= 1
    print(pt + 1, end=' ')
    seg.apply(0, perm2[i], 1)