### anurag_orz's blog

By anurag_orz, history, 6 weeks ago, 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 Comments (11)
 » One idea for a solution: binary search on a segment tree.
•  » » 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?
 » 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.
•  » » 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
•  » » » 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].
•  » » » » 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???
 » 5 weeks ago, # | ← Rev. 5 →   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
 » 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?sum(l, r) = sm = tree.query(l, r)sm = sum — number of zeros in range (l, r). (use array C)if sm < (r-l+1) decrease r; else increase l resource
•  » » I'm confused, where did we maintain the negative values' indexes?
•  » » » Look at step 1, B[i] = 1 if A[i] > 0; else B[i] = 0; (A[i] <= 0)
 » 5 weeks ago, # | ← Rev. 3 →   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}$