Duukh's blog

Does This problem required knowing Segment Tree Beats ?
By Duukh, history, 17 months ago, In English

Given an array of size n <= 10^5 initially filed with zeros, answer two types of queries:

1 A B C : Perform the following operation arr[i] = max(arr[i],C) , where i = A (MOD B) and 1 <= i <= n .

2 I : Print value arr[I] .

Constraints : 1 <= A < B <= N and C <= 10^9

1 <= I <= N .

1 <= n , q <= 10^5 .

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

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Duukh (previous revision, new revision, compare).

→ Reply
»
17 months ago, # |
  Vote: I like it +58 Vote: I do not like it

No; in fact I'm not sure segtree beats would be especially helpful since we aren't performing range updates here.

This problem can be solved via sqrt decomposition. Pick some K near the square root of N and directly apply all updates with B > K. Then maintain a table storing the highest update so far for all (A, B) with B < K. We can answer queries by computing the best answer for each B < K and comparing to the precomputed answer across all B > K.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Thank you so much for your time .

    → Reply
»
17 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I am confused, I don't see any range query here, shouldn't this be possible in O(n) without following any DS?

→ Reply
»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

can you give the link to the question?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that i==A (mod B) is a more clear notation

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the source for this problem? I'd like to submit it

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Duukh (previous revision, new revision, compare).

→ Reply