OneClickAC's blog

Problems with range updates and query
By OneClickAC, 7 years ago, In English

Hello CF community,

I have a problem and I don't know how to solve it. Some time back, I took help from some amazing people on codeforces for a problem about finding frequency of a number in a range from l to r. The blog for the same is this — http://codeforces.me/blog/entry/52578

I was wondering about how can we solve the same problem given we have to keep an eye on updates also this time. The updates are basically range updates (adding x from l to r).

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help please?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can do it in per query.

The idea is briefly described here (problem E analysis)

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

    The time complexity mentioned in the editorial is not .

    Its

    It will not pass when q and n both will be allowed values till 1e5.

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

      Well, I said “per query”.

      It’s quite strange to set the restrictions before you come up with a solution that is guaranteed to pass within them, lol :)

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

        Oh! My bad. Sorry I didn't see that "per query" thing.

        Generally the constraints for these problems are the same as I mentioned, that is why I wrote so and the solution available in the editorial is nice but probably it won't be able to pass in most cases.

        → Reply