SHOToRSAVARE_KAZEMSHAHR's blog

segment
By SHOToRSAVARE_KAZEMSHAHR, history, 5 years ago, In English

Hi (; do we have a segment that handle these two queries? 1 : l r d : add an integer d to all elements whose indexes belong to the interval from l to r d<1 2 : l r : how many elements between l and r are bigger than x(x is fixed)

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If x is fixed you can maintain two segment trees. First one is just simple add and get maximum. After each add operation you query for maximum on the whole sequence and until it’s greater than x add +1 on the second tree in corresponding place and add -inf on this place in the first tree. Complexity O((n+q)logn)

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I don’t know what to do if d is integer instead of natural. However, I don't think that kobor's complexity is correct. You use a lazy sum segtree with query for max. For question 2 you use a second segtree for sum query. For question 1 you update the lazy segtree. As he said, we need to find the numbers which weren’t bigger than x previously and now are. So while the query for the maximum is >x we search for the leftmost number in the interval that is >x (binary search the maximum length query with the left end == l that returns <=x, (this is O(log^2(n)) and we don’t know how many times we perform it)), then lazy update the index (i) we found with –inf to eliminate it, and update the i th position in the second segtree to 1. In worst case the complexity would be O(n*log^2(n)+q*log(n))

Do you have a problem link?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    You can have a segment and for each node save max and the left most index You can handle these queries

    121 E is similar to this problem

    → Reply