You are not logged in. Please login at www.codechef.com to post your questions!

×

Need help In a segment tree problem

Given an array of N(N<=10^5) elements and -10^9<=A[i]<=10^9. Q(Q<=10^5) queries are there of two types:

  1. L R K: Add K to all numbers in range [L,R] in array.
  2. L R: Find no. of positive elements>0 in range [L,R].

I Thought of segment tree with lazy propagation but not able to understand what info to be stored in each node. Please suggest some approach for this problem. @freeloop

asked 30 May, 19:34

lakh's gravatar image

4★lakh
1395
accept rate: 23%

edited 30 May, 20:20

Please provide some idea for this problem. No progress till now.

(30 May, 23:08) lakh4★

U can do this using parallel binary search.

Read this:

http://codeforces.com/blog/entry/45578?mobile=false

(Just see after which update query of first type ,a particular element becomes positive)

If u have any doubts,u can ask,i'll elaborate it.

(31 May, 02:05) vivek_19982996★

@vivek_1998299 can u validate my approach?

(31 May, 13:30) dishant_185★

I am not at all sure about this. Any counter case/feedback is appreciated!
I think you can solve this problem by maintaining a Venice Set in each node. I learned this thing just few days back and so may be I am completely wrong! From here on, I assume you have atleast had a look on the blog I mentioned.
My thought:
Query of type 1 : We can use Technique as mentioned in blog with lazy propagation.
Query of type 2 : We basically need to find numbers > water_level in Set of range [L,R]. As the values are stored in multiset, we can binary search on value of water_level to find the answer.

link

answered 30 May, 21:29

dishant_18's gravatar image

5★dishant_18
61419
accept rate: 12%

edited 30 May, 21:32

can u explain it in a more detail?

i mean how would u handle the range part?

(31 May, 13:54) vivek_19982996★

Ohh nvm, I just figured that this approach won't work due to mismatch of water_level between children of a node. Thanks though :)

(31 May, 15:23) dishant_185★

Thanx for telling about this new data structure:)

(31 May, 16:15) vivek_19982996★

Glad my wrong approach/answer was helpful to someone xD

(31 May, 16:58) dishant_185★

Can you share question link?

link

answered 30 May, 19:46

vikram_91's gravatar image

4★vikram_91
112
accept rate: 0%

Actually my friend asked me this problem some days ago.

(30 May, 19:48) lakh4★

I think you will need a range min query and range max query based 2 segment trees and using that you can answer the queries.

e.g. if max element in a range is less than 0 you return 0, if min element in a range is greater than 0 you return r - l + 1. else you go to the next level and see if one of the above condition holds.

Use lazy propagation to update the maximum and minimum values of the 2 trees. That shouldn't be too hard.

link

answered 30 May, 20:44

satvik007's gravatar image

5★satvik007
11
accept rate: 0%

array A[]= -1 1 -1 1 -1 1.......-1 1

and query [1:N]

in this case complexity would be O(N) per query

(30 May, 20:59) vivek_19982996★

@vivek_1998299 can you suggest some optimization or some other approach??

(30 May, 21:17) lakh4★

How will it be O(N logN) in the case Vivek pointed out?

(30 May, 21:58) dishant_185★

Yeah my bad. It is N + N / 2 + N / 4 ... < 2 * N

(30 May, 22:11) satvik0075★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×825
×685
×110
×65

question asked: 30 May, 19:34

question was seen: 257 times

last updated: 31 May, 16:58