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

Автор adyyy, история, 4 года назад, По-английски

Hi, if there is a problem such that we are given an array of size (1<=n<=1e5) and queries (1<=q<=1e5) , int each query we are given a range [L,R] and we have to tell that if the array is increasing in that range or not . Also if we had a query for point update can this be solved ???? I was solving https://www.codechef.com/problems/DELSORT this problem so just thought about this question . I dont know if similar question already exists , if it does please provide link . Thanks .

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yes, this is solvable: the queries are equivalent to "is $$$[l, r - 1]$$$ in the difference array all-positive" which can be solved using a segment tree. The point updates don't break this solution either: a point update only changes 2 elements of the difference array so you can do 2 point updates in the constructed segment tree.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    is there any such problem , i dont know about how to apply segment tree here in this problem .

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

I think we can solve it using Fenwick tree

Here is my solution -->

Traverse the array and check if(A[i]>A[i-1]) then update value for i to be 1 using update operation other wise keep it 0.

for the subarray(l,r) to be increasing sum(r) — sum(l) == r-l; (NOTE: we have take l not l-1)

for point update just check it with its neighbouring elements and update accordingly.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yeah i think this is right apporach . thanks for helping buddy

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I have a slightly easier way with a Segtree:

    We can check that $$$a_{i-1} < a_i$$$ for $$$1 \leq i < N$$$ (0-based indexing), and use the bitwise AND to check a subarray.

    For the updates. we can simply check the elements around the update, and fix them accordingly, like you and -is-this-fft- explained.