This approach is in O(n) i tried to find better approcah // https://www.geeksforgeeks.org/find-the-occurrences-of-y-in-the-range-of-x/
but I cannt find any approch please suggest me..
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
This approach is in O(n) i tried to find better approcah // https://www.geeksforgeeks.org/find-the-occurrences-of-y-in-the-range-of-x/
but I cannt find any approch please suggest me..
Name |
---|
Let $$$f_{x,y}$$$ be the quantity of digits $$$y$$$ among numbers $$$[0, x]$$$.
Then to answer the query $$$l, r, d$$$ is simply $$$f_{r,d} - f_{l-1,d}$$$.
Preprocissing is $$$O(n * log_{10}n)$$$, and each query if $$$O(1)$$$.
So the total complexity is $$$O(n * log_{10}n + q)$$$.
By the way, I think there's a more efficient way to solve this problem:
at first read https://codeforces.com/blog/entry/77096 if you aren't familiar with digit dp.
After this we have a $$$dp_{i,j,flag} - $$$ quantity of numbers of length $$$i$$$ with $$$j$$$ digits $$$x$$$, and flag tells us whether our prefix of length $$$i$$$ is equal to prefix of length $$$i$$$ of number $$$n$$$ (you can read about it more in the blog I mentioned above).
Time complexity is $$$O(log_{10}n)$$$
Lets all digits we have to check is in range $$$[head, tail]$$$ where $$$head$$$ can simply be $$$0$$$ (first index of vector, array, etc in C++)
Lets
magic(int pos, bool isLess, int cnt)
is the current number with digits range $$$(head, pos)$$$ are build and the part $$$(head, pos)$$$ is currently less than digits range $$$(head, pos)$$$ of $$$n$$$ if ($$$isLess$$$ true) which $$$cnt$$$ digits $$$x$$$If $$$isLess$$$ is true then we can chose what ever digit in range $$$[0, 9]$$$ we want since the number we selecting is already smaller than $$$n$$$
If $$$isLess$$$ is false then we can only chose digit that not greater than $$$n[pos]$$$ which is in range $$$[0, n[pos]]$$$
If selected digit is $$$x$$$ then we increase the counter for next recursive by one
If selected digit is smaller than $$$n[digit]$$$ then $$$isLess$$$ of the next recursive will be true
If current selected digit is in position $$$tail$$$, then we return $$$cnt$$$, which is the number of digit $$$x$$$ appear in the number we built so far
Then after all, we just need to add memorization of 3 dimentional: $$$f[pos][isLess][cnt]$$$. If it is calculated than we just need to return the value, else keep calculating and update current dp function $$$f[][][]$$$