adyyy's blog

Query Problem!!!!
By adyyy, history, 4 years ago, In English

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 .

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply