Given an integer $$$n$$$, the next line contains $$$n$$$ integer. Third line contains an integer $$$q$$$. The next $$$q$$$ lines, contains $$$q$$$ queries. Query format is $$$l_i$$$, $$$r_i$$$. You have to answer to queries like this. If all the numbers that are less or equal than its index, that is, $$$a_l$$$ $$$≤$$$ $$$0$$$, $$$a_{l + 1}$$$ $$$≤$$$ $$$1$$$, $$${...}$$$, $$$a_r$$$ $$$≤$$$ $$${r - l}$$$.
Constraints are $$$n$$$ $$$≤$$$ $$$2 ⋅ {10 ^ 5}$$$, $$$q$$$ $$$≤$$$ $$$2 ⋅ {10 ^ 5}$$$.
Can you help me to solve this problem?
Auto comment: topic has been updated by tuncypasha (previous revision, new revision, compare).
.
Can you give constraints on values of the $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ? (upper + lower bound)
Anyway, no need for them.
Solution :
for query $$$[l,r]$$$ , we can rewrite it as $$$a_i\le i-l$$$ for $$$i \in [l,r]$$$, this is equivalent to $$$a_i-i\le -l$$$. So you just need to RMQ (maximum) $$$a_i-i$$$ in $$$[l,r]$$$, and check if it's less than $$$-l$$$.
can you tell me the time complexity of the solution i think it is n2
i got it thanks
Use a segment tree and it would be done in $$$O(logn)$$$ per query, or you can use a sparse table, and manage to do it in $$$O(1)$$$ per query with $$$O(nlogn)$$$ precomputation.
Constraints are $$$a_i$$$ $$$≤$$$ $$$10 ^ 9$$$
https://mirror.codeforces.com/problemset/problem/1736/C1
similar problem...