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).
Can anybody help please?
You can do it in
per query.
The idea is briefly described here (problem E analysis)
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.
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 :)
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.