anurag_orz's blog

By anurag_orz, history, 6 weeks ago, In English

Given an array A of length N, perform Q queries of 2 types in it
Query 1 — L R given, flip signs of array elements (positive to negetive and vice versa) from L to R
Query 2 — L R given, print index of first negetive element in L to R
Constraints —
N,Q <=2 * 10 ^ 5
-1e8 <= A[i] <= 1e8
Sorry for poor English

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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

One idea for a solution: binary search on a segment tree.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but imo every 1 index update in segment tree takes logN(approx) time so L to R index updates will take NlogN time? do we have to use lazy propagation?

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I think we can do it using a segment tree
if we have the index of the first positive and first negative elements of the range [L, R] and we apply Query of type 1, then the first positive element will become the first negative and vice-versa.
correct me if I am wrong.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A = {1,-1,2,-2,3,-3}
    1 to 4 index first positve = 1 index
    1 to 4 index first negetive = 2 index
    3 to 4 index first positive = 3 index
    3 to 4 index first negetive = 4 index

    Query 1 applied on 1 to 4 index
    as per your logic we will change values
    1 to 4 index first positve changed to = 2 index
    1 to 4 index first negetive changed to = 1 index

    now for Query of type 2 for 1 to 4 index, first negetive = 2 index correct,
    but now for Query of type 2 for 3 to 4 index, we are again printing index 4 as it's not updated, but it should be 3.
    sorry for poor english

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but that's what segment tree will do for us.
      when you run Query 1 for range [L, R] it will not just do for [L, R], it will do for everything between [L, R].

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        imo segment tree updates value of a single index in logN and then that update is reflected in L to R
        not for complete L to R index in single update, then what will be difference between lazy propagation over segment tree and normal segment tree???

        Can you please provide code of it???

»
6 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Use a segtree and store 2 values in every node, $$$p^+ = \text{(The first positive element in the segment)}, p^- = \text{(The first negative element in the segment)}$$$. Also store a lazytag $$$inv= \text{(1 if the segment should be flipped, 0 if not)}$$$.

When merging two segments to make a bigger one, just take the minimum of each corresponding $$$p^+$$$ and $$$p^-$$$.

When doing the range modification, find the corresponding $$$\log N$$$ segments in the tree and swap $$$p^+$$$ and $$$p^-$$$, then flip $$$inv$$$. You can propagate the lazytags down the same way.

(the weights of $$$a_i$$$ are useless in this problem lol)

C++ implementation, may have bugs because I only tested a few samples on it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Try segment tree with lazy propagation.

step 1: Construct new array B using given array A as B[i] = A[i] > 0 ? 1 : 0 and construct another array C to track zeros in A, C[i] = A[i] == 0 ? 1 : 0 and do prefix sum of C to get number of zeros in range.

step 2: Construct a segment tree with lazy propagation (tree) using array B to sum in of elements in the range.

step 3: For query type 1, do xor with 1 in a given range.

step 4: For query type 2, do a binary search in the segment tree to get the first zero in the range.

How to do a binary search?
resource
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm confused, where did we maintain the negative values' indexes?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Look at step 1, B[i] = 1 if A[i] > 0; else B[i] = 0; (A[i] <= 0)

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

We can do it with Segment Tree with Lazy Propagation.

Let, positive to be 0 and negative to be 1.

  • For 1st operation, $$$+1$$$ in $$${[L...R]}$$$ with taking %$$$2$$$ (modulo with 2). (It will flip 0 to 1 and vice versa)
  • For 2nd operation just do a binary search in range $$${[L...R]}$$$ and find the minimum index $$$i$$$ such that $$${(\sum_{j = L}^{i} a_j) \ge 1}$$$ that is $$${pref_i - pref_{L-1} \ge 1}$$$