Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя AdarshBhaiyaNeICPCPela

Автор AdarshBhaiyaNeICPCPela, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

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 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

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.