Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

SecretSuperstar's blog

By SecretSuperstar, 12 months 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.com/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  

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

Can anybody help please?

»
12 months ago, # |
  Vote: I like it -10 Vote: I do not like it

nobody will. Ha Ha

»
12 months 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)

  • »
    »
    12 months 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.

    • »
      »
      »
      12 months 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 :)

      • »
        »
        »
        »
        12 months 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.