[Solution] Good Subarrays (Hard Version) solution codeforces

Good Subarrays (Hard Version) solution codeforces – 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 𝑏𝑖𝑖bi≥i for all 𝑖i (1𝑖𝑚1≤i≤m).

Table of Contents

[Solution] Good Subarrays (Hard Version) solution codeforces

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𝑝,𝑥𝑛1≤p,x≤n). You have to do 𝑎𝑝:=𝑥ap:=x (assign 𝑥x to 𝑎𝑝ap). In the updated array, find the number of pairs of indices (𝑙,𝑟)(l,r), where 1𝑙𝑟𝑛1≤l≤r≤n, such that the array [𝑎𝑙,𝑎𝑙+1,,𝑎𝑟][al,al+1,…,ar] 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𝑛21051≤n≤2⋅105).

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛1≤ai≤n).

The third line contains an integer 𝑞q (1𝑞21051≤q≤2⋅105) — the number of queries.

Each of the next 𝑞q lines contains two integers 𝑝𝑗pj and 𝑥𝑗xj (1𝑝𝑗,𝑥𝑗𝑛1≤pj,xj≤n) – the description of the 𝑗j-th query.

[Solution] Good Subarrays (Hard Version) solution codeforces

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

Examples
input

Copy
4
2 4 1 4
3
2 4
3 3
2 1
output

Copy
6
10
5
input

Copy
5
1 1 3 2 1
3
1 3
2 5
4 5
output

Copy
7
9
8

[Solution] Good Subarrays (Hard Version) solution codeforces

Here are notes for first example.

In first query, after update 𝑎=[2,4,1,4]a=[2,4,1,4]. Now (1,1)(1,1)(2,2)(2,2)(3,3)(3,3)(4,4)(4,4)(1,2)(1,2), and (3,4)(3,4) are suitable pairs.

In second query, after update 𝑎=[2,4,3,4]a=[2,4,3,4]. Now all subarrays of 𝑎a are good.

In third query, after update 𝑎=[2,1,1,4]a=[2,1,1,4]. Now (1,1)(1,1)(2,2)(2,2)(3,3)(3,3)(4,4)(4,4), and (3,4)(3,4) are suitable.

 

For Solution

“Click Here”

Leave a Comment