Good Subarrays (Hard Version) (Codeforces 1736C2)
Tags: DP, two pointers

This is the hard version of this problem. In this version, we have queries. Note that we do not have multiple test cases in this version. You can make hacks only if both versions of the problem are solved.An array $$$b$$$ of length $$$m$$$ is good if for all $$$i$$$ the $$$i$$$-th element is greater than or equal to $$$i$$$. In other words, $$$b$$$ is good if and only if $$$b_i \geq i$$$ for all $$$i$$$ ($$$1 \leq i \leq m$$$).You are given an array $$$a$$$ consisting of $$$n$$$ positive integers, and you are asked $$$q$$$ queries. In each query, you are given two integers $$$p$$$ and $$$x$$$ ($$$1 \leq p,x \leq n$$$). You have to do $$$a_p := x$$$ (assign $$$x$$$ to $$$a_p$$$). In the updated array, find the number of pairs of indices $$$(l, r)$$$, where $$$1 \le l \le r \le n$$$, such that the array $$$[a_l, a_{l+1}, \ldots, a_r]$$$ is good.Note that all queries are independent, which means after each query, the initial array $$$a$$$ is restored. 

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).The third line contains an integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.Each of the next $$$q$$$ lines contains two integers $$$p_j$$$ and $$$x_j$$$ ($$$1 \leq p_j, x_j \leq n$$$) – the description of the $$$j$$$-th query.

Output: For each query, print the number of suitable pairs of indices after making the change. 

Note: Here are notes for first example.In first query, after update $$$a=[2,4,1,4]$$$. Now $$$(1,1)$$$, $$$(2,2)$$$, $$$(3,3)$$$, $$$(4,4)$$$, $$$(1,2)$$$, and $$$(3,4)$$$ are suitable pairs.In second query, after update $$$a=[2,4,3,4]$$$. Now all subarrays of $$$a$$$ are good.In third query, after update $$$a=[2,1,1,4]$$$. Now $$$(1,1)$$$, $$$(2,2)$$$, $$$(3,3)$$$, $$$(4,4)$$$, and $$$(3,4)$$$ are suitable.

Sample Inputs:
4
2 4 1 4
3
2 4
3 3
2 1

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

Sample Outputs:
6
10
5

7
9
8

Solution (Python):
class RMQMIN:

    def __init__(self, arr):
        self.arr = arr
        MAXN = len(arr)
        self.log2 = [0] * (MAXN + 1)
        i = 0
        while 2 ** i < MAXN + 1:
            self.log2[2 ** i] = i
            i += 1
        for i in range(1, MAXN + 1):
            if self.log2[i] == 0:
                self.log2[i] = self.log2[i - 1]
        K = self.log2[MAXN] + 1
        self.lookup = [0] * ((K + 1) * MAXN)
        self.M = K + 1
        self.buildSparseTable()

    def buildSparseTable(self):
        n = len(self.arr)
        for i in range(0, n):
            self.lookup[i * self.M] = self.arr[i]
        j = 1
        while 1 << j <= n:
            i = 0
            while i + (1 << j) - 1 < n:
                self.lookup[i * self.M + j] = min(self.lookup[i * self.M + j - 1], self.lookup[(i + (1 << j - 1)) * self.M + j - 1])
                i += 1
            j += 1

    def query(self, L, R):
        j = self.log2[R - L + 1]
        return min(self.lookup[L * self.M + j], self.lookup[(R - (1 << j) + 1) * self.M + j])

def main():
    n = int(input())
    a = readIntArr()
    dp1 = [0] * n
    for i in range(n):
        if i - 1 >= 0:
            prev = dp1[i - 1]
        else:
            prev = 0
        dp1[i] = min(prev + 1, a[i])
    prefixdp1 = dp1.copy()
    for i in range(1, n):
        prefixdp1[i] += prefixdp1[i - 1]
    levela = []
    for i in range(n):
        levela.append(a[i] - i)
    rmqminlevela = RMQMIN(levela)

    def findnext(i, x):
        (lo, hi) = (i, n - 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if rmqminlevela.query(i + 1, mid) >= x - i:
                lo = mid
            else:
                hi = mid - 1
        return lo + 1
    suffixdp2 = [0] * n
    for i in range(n - 1, -1, -1):
        j = findnext(i, a[i])
        cnts = j - i
        lastterm = a[i] + cnts - 1
        suffixdp2[i] = (a[i] + lastterm) * cnts // 2
        if j < n:
            suffixdp2[i] += suffixdp2[j]
    q = int(input())
    allans = []
    for _ in range(q):
        (i, x) = readIntArr()
        i -= 1
        first = 0
        if i - 1 >= 0:
            first = prefixdp1[i - 1]
        if i == 0:
            prev = 0
        else:
            prev = dp1[i - 1]
        x = min(x, prev + 1)
        j = findnext(i, x)
        cnts = j - i
        lastterm = x + cnts - 1
        second = (x + lastterm) * cnts // 2
        third = 0
        if j < n:
            third = suffixdp2[j]
        ans = first + second + third
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys
input = sys.stdin.readline
inf = float('inf')

def getInt():
    return int(input())

def getStr():
    return input().strip()

def getList(split=True):
    s = getStr()
    if split:
        s = s.split()
    return map(int, s)
t = 1

def solve():
    n = getInt()
    a = list(getList())
    j = res = 0
    p = [0] * n
    P = [0] * n
    from bisect import bisect_left
    f = {}
    for (i, x) in enumerate(a):
        j = max(j, i)
        while j < n and a[j] >= j + 1 - i:
            j += 1
        res += j - i
        if j - 1 not in f:
            f[j - 1] = i
            J = j + 1
        while J < n and a[J] >= J + 1 - i:
            J += 1
        p[i] = p[i - 1] + j - 1
        P[i] = P[i - 1] + J - j
    q = getInt()

    def calc(l, r, p):
        if l > r:
            return 0
        res = p[r]
        if l:
            res -= p[l - 1]
        return res
    keys = sorted(f.keys())
    for _ in range(q):
        (u, v) = getList()
        u -= 1
        ans = res
        it = bisect_left(keys, u)
        if v < a[u]:
            it = keys[it]
            l = max(f[it], u + 1 - v)
            ans -= calc(f[it], l - 1, p) - (u - 1) * (l - f[it])
        elif v > a[u]:
            if it and keys[it - 1] + 1 == u:
                l = max(f[keys[it - 1]], u + 1 - v)
                ans += calc(l, f[keys[it]] - 1, P)
        print(ans)
for _ in range(t):
    solve()

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= i + 1
js = [0] * n
extends = [0] * n
j = 0
jj = 0
ans = 0
for i in range(n):
    threshold = -i
    while j < n and a[j] >= threshold:
        j += 1
    js[i] = j
    jj = max(jj, min(n, j + 1))
    while jj < n and a[jj] >= threshold:
        jj += 1
    extends[i] = jj - j
    ans += j - i
psumj = [0] * (n + 1)
for i in range(n):
    psumj[i + 1] = psumj[i] + js[i]
psumextend = [0] * (n + 1)
for i in range(n):
    psumextend[i + 1] = psumextend[i] + extends[i]
q = int(input())
for _ in range(q):
    (p, x) = map(int, input().split())
    p -= 1
    x -= p + 1
    updated_ans = ans
    if x < a[p]:
        maxi = min(p, -x - 1)
        if maxi >= 0:
            i = bisect.bisect_right(js, p, lo=0, hi=maxi + 1)
            updated_ans -= psumj[maxi + 1] - psumj[i] - p * (maxi - i + 1)
    elif x > a[p]:
        mini = max(-x, 0)
        maxi = p
        if maxi >= mini:
            il = bisect.bisect_left(js, p, lo=mini, hi=maxi + 1)
            ir = bisect.bisect_right(js, p, lo=mini, hi=maxi + 1)
            updated_ans += psumextend[ir] - psumextend[il]
    print(updated_ans)