When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

OneClickAC's blog

By OneClickAC, 6 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.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

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help please?

»
6 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)

  • »
    »
    6 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.

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

      • »
        »
        »
        »
        6 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.