Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

AdarshBhaiyaNeICPCPela's blog

By AdarshBhaiyaNeICPCPela, history, 7 years ago, In English

Given an array of $$$n$$$ integers, with $$$1 \le a_i \le 10^6$$$, and given queries of type $$$(l, r)$$$, find whether, if we delete all the elements of the array such that $$$l \le a_i \le r$$$, the resultant array will form a non-decreasing sequence. We need to answer these queries in $$$O(1)$$$ time complexity.

How to do this problem?

»
7 years ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

count number of inversions from these elements (including inversions going in the reverse direction)

range query and sum and if its equal to total inversions then yes else no

»
7 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Create an array p that p[i]={a[i],i} and sort it ascending.

Find L which is the farthest position from the left where the sequence from p[1].second to p[L].second is ascending, and R which is the farthest position from the right where the sequence from p[R].second to p[n].second is ascending.

Which each query l,r, it's possible if l<=p[L].first && r>=p[R].first and vise versa.