Original link: https://blog.chungzh.cn/articles/luogu-p4755/
Title meaning
Small D has a sequence ${a}$, when a number pair $(i,j)$ ($i \le j$) satisfies the product of $a_i$ and $a_j$ is not greater than $a_i, a_{i+1 }, \ldots, a_j$, Little D thinks this pair is beautiful. Please find the number of beautiful pairs.
$1\le n\le{10}^5$, $1\le a_i\le{10}^9$.
problems while programming
- Not familiar with ST tables!
- What’s more, there is a problem with the understanding of
lower_boundandupper_bound. Let’s review the elementary school knowledge:lower_boundis to find the position of “greater than or equal to”,upper_boundis “greater than”. When I was writing this question, I usedlower_boundinexplicably to find a position less than a certain number, and there was no-1.
In summary, I am zz.
train of thought
Consider divide and conquer (it is said that this is a routine), we find the maximum position $mid$ in an interval $[l, r]$, then count all the answers across $mid$, and then recursively process $[l, mid -1], [mid+1, r]$. Suppose the number on the left of $mid$ is $a_i$, and the number on the right is $a_j$. According to the title, $a_i * a_j \le a_{mid}$, that is, $a_j \le \lfloor\frac{a_{mid}} {a_i}\rfloor$. Then we enumerate $a_i$, and then use the chairman tree to count the number of numbers less than $\lfloor\frac{a_{mid}}{a_i}\rfloor$ in the right interval.
Note that the smaller length of the left and right intervals needs to be enumerated each time, so that $O(n\log^2n)$ can be achieved. Otherwise it will be stuck as $O(n^2\log n)$.
|
|
This article is transferred from: https://blog.chungzh.cn/articles/luogu-p4755/
This site is only for collection, and the copyright belongs to the original author.