Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

How to handle this range query problem??

Правка en1, от Lakh, 2018-05-31 06:06:58

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.

Теги array, segment-tree, queries

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Lakh 2018-05-31 06:06:58 421 Initial revision (published)