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
One idea for a solution: binary search on a segment tree.
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???
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 asB[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, doxor 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.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
Link1
Link2
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)
We can do it with Segment Tree with Lazy Propagation.
Let, positive to be 0 and negative to be 1.