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.

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???

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

resourceLink1

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.