Fixed Point Removal (Codeforces 1404C)
Tags: Greedy, two pointers

Let $$$a_1, \ldots, a_n$$$ be an array of $$$n$$$ positive integers. In one operation, you can choose an index $$$i$$$ such that $$$a_i = i$$$, and remove $$$a_i$$$ from the array (after the removal, the remaining parts are concatenated).The weight of $$$a$$$ is defined as the maximum number of elements you can remove.You must answer $$$q$$$ independent queries $$$(x, y)$$$: after replacing the $$$x$$$ first elements of $$$a$$$ and the $$$y$$$ last elements of $$$a$$$ by $$$n+1$$$ (making them impossible to remove), what would be the weight of $$$a$$$?

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$)  — the length of the array and the number of queries.The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq n$$$) — elements of the array.The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$x, y \ge 0$$$ and $$$x+y < n$$$).

Output: Print $$$q$$$ lines, $$$i$$$-th line should contain a single integer  — the answer to the $$$i$$$-th query.

Note: Explanation of the first query:After making first $$$x = 3$$$ and last $$$y = 1$$$ elements impossible to remove, $$$a$$$ becomes $$$[\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times]$$$ (we represent $$$14$$$ as $$$\times$$$ for clarity).Here is a strategy that removes $$$5$$$ elements (the element removed is colored in red):  $$$[\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times]$$$  $$$[\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times]$$$  $$$[\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times]$$$  $$$[\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times]$$$  $$$[\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times]$$$  $$$[\times, \times, \times, 9, 4, 5, 3, \times]$$$ (final state) It is impossible to remove more than $$$5$$$ elements, hence the weight is $$$5$$$.

Sample Inputs:
13 5
2 2 3 9 5 4 6 5 7 8 3 11 13
3 1
0 0
2 4
5 0
0 12

5 2
1 4 1 2 4
0 0
1 0

Sample Outputs:
5
11
6
1
0

2
0

Solution (Python):
mod = 1000000007
eps = 10 ** (-9)

def main():
    import sys
    input = sys.stdin.buffer.readline

    class Bit:

        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            x = 0
            k = 1 << self.size.bit_length() - 1
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1
    (N, Q) = map(int, input().split())
    A = list(map(int, input().split()))
    A = [i + 1 - A[i] for i in range(N)]
    query = [[] for _ in range(N + 1)]
    ans = [0] * Q
    for q in range(Q):
        (x, y) = map(int, input().split())
        l = x + 1
        r = N - y
        query[r].append((l, q))
    bit = Bit(N + 1)
    for r in range(1, N + 1):
        a = A[r - 1]
        if a == 0:
            bit.add(1, -1)
            bit.add(r + 1, 1)
        elif a > 0:
            k = bit.lower_bound(-a + 1)
            if k <= r:
                bit.add(1, -1)
                bit.add(k, 1)
        for (l, q) in query[r]:
            ans[q] = -bit.sum(l)
    print(*ans, sep='\n')
if __name__ == '__main__':
    main()

Solution (Python):
from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
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')

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())
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
farr = [1]
ifa = []

def fact(x, mod=0):
    if mod:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr) % mod)
    else:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr))
    return farr[x]

def ifact(x, mod):
    global ifa
    ifa.append(pow(farr[-1], mod - 2, mod))
    for i in range(x, 0, -1):
        ifa.append(ifa[-1] * i % mod)
    ifa = ifa[::-1]

def per(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return fact(i) // fact(i - j)
    return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return per(i, j) // fact(j)
    return per(i, j, mod) * ifa[j] % mod

def catalan(n):
    return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
    while l < r:
        mid = (l + r) // 2
        if t > f(mid):
            l = mid + 1
        else:
            r = mid
    return l

def rinc(f, t, l, r):
    while l < r:
        mid = (l + r + 1) // 2
        if t < f(mid):
            r = mid - 1
        else:
            l = mid
    return l

def ldec(f, t, l, r):
    while l < r:
        mid = (l + r) // 2
        if t < f(mid):
            l = mid + 1
        else:
            r = mid
    return l

def rdec(f, t, l, r):
    while l < r:
        mid = (l + r + 1) // 2
        if t > f(mid):
            r = mid - 1
        else:
            l = mid
    return l

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def binfun(x):
    c = 0
    for w in arr:
        c += ceil(w / x)
    return c

def lowbit(n):
    return n & -n

def inverse(a, m):
    a %= m
    if a <= 1:
        return a
    return (1 - inverse(m, a) * m) // a % m

class BIT:

    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr) - 1

    def update(self, x, v):
        while x <= self.n:
            self.arr[x] += v
            x += x & -x

    def query(self, x):
        ans = 0
        while x:
            ans += self.arr[x]
            x &= x - 1
        return ans

class smt:

    def __init__(self, l, r, arr):
        self.l = l
        self.r = r
        self.value = (1 << 31) - 1 if l < r else arr[l]
        mid = (l + r) // 2
        if l < r:
            self.left = smt(l, mid, arr)
            self.right = smt(mid + 1, r, arr)
            self.value &= self.left.value & self.right.value

    def setvalue(self, x, val):
        if self.l == self.r:
            self.value = val
            return
        mid = (self.l + self.r) // 2
        if x <= mid:
            self.left.setvalue(x, val)
        else:
            self.right.setvalue(x, val)
        self.value = self.left.value & self.right.value

    def ask(self, l, r):
        if l <= self.l and r >= self.r:
            return self.value
        val = (1 << 31) - 1
        mid = (self.l + self.r) // 2
        if l <= mid:
            val &= self.left.ask(l, r)
        if r > mid:
            val &= self.right.ask(l, r)
        return val

class DSU:

    def __init__(self, n):
        self.c = [-1] * n

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def find(self, x):
        if self.c[x] < 0:
            return x
        self.c[x] = self.find(self.c[x])
        return self.c[x]

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if u == v:
            return False
        if self.c[u] < self.c[v]:
            (u, v) = (v, u)
        self.c[u] += self.c[v]
        self.c[v] = u
        return True

    def size(self, x):
        return -self.c[self.find(x)]

class UFS:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv

def Prime(n):
    c = 0
    prime = []
    flag = [0] * (n + 1)
    for i in range(2, n + 1):
        if not flag[i]:
            prime.append(i)
            c += 1
        for j in range(c):
            if i * prime[j] > n:
                break
            flag[i * prime[j]] = prime[j]
            if i % prime[j] == 0:
                break
    return prime

def dij(s, graph):
    d = {}
    d[s] = 0
    heap = [(0, s)]
    seen = set()
    while heap:
        (dis, u) = heappop(heap)
        if u in seen:
            continue
        for v in graph[u]:
            if v not in d or d[v] > d[u] + graph[u][v]:
                d[v] = d[u] + graph[u][v]
                heappush(heap, (d[v], v))
    return d

def GP(it):
    return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None
t = 1
for i in range(t):
    (n, q) = RL()
    a = RLL()
    a = [i + 1 - a[i] for i in range(n)]
    ans = [0] * q
    res = [[] for i in range(1 + n)]
    for i in range(q):
        (x, y) = RL()
        (l, r) = (x + 1, n - y)
        res[r].append((i, l))
    bi = BIT([0] * (n + 1))
    for r in range(1, n + 1):
        if a[r - 1] >= 0:
            (lo, hi) = (0, r)
            while lo < hi:
                mid = (lo + hi + 1) // 2
                tmp = bi.query(n - mid + 1)
                if tmp >= a[r - 1]:
                    lo = mid
                else:
                    hi = mid - 1
            if lo:
                bi.update(n - lo + 1, 1)
        for (i, l) in res[r]:
            ans[i] = bi.query(n - l + 1)
    for x in ans:
        print(x)
''

Solution (Python):
""""""
mod = 1000000007
eps = 10 ** (-9)

def main():
    import sys
    input = sys.stdin.readline

    class Bit:

        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            x = 0
            k = 1 << self.size.bit_length() - 1
            while k:
                if x + k <= self.size and self.tree[x + k] > w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1
    (N, Q) = map(int, input().split())
    A = list(map(int, input().split()))
    A = [i + 1 - A[i] for i in range(N)]
    query = [[] for _ in range(N + 1)]
    ans = [0] * Q
    for q in range(Q):
        (x, y) = map(int, input().split())
        l = x + 1
        r = N - y
        query[r].append((l, q))
    bit = Bit(N + 1)
    for r in range(1, N + 1):
        a = A[r - 1]
        if a == 0:
            bit.add(1, +1)
            bit.add(r + 1, -1)
        elif a > 0:
            k = bit.lower_bound(a - 1)
            bit.add(1, +1)
            bit.add(k, -1)
        for (l, q) in query[r]:
            ans[q] = bit.sum(l)
    print(*ans, sep='\n')
if __name__ == '__main__':
    main()