| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
A function F(l, r) is defined as follow:
F(l, r) = 0 if l > r
else m is the index of the largest element from l to r.
F(l, r) = r — l + 1 + F(l, m — 1) + F(m + 1, r)
Given a permutation of length N and Q queries (l, r), calculate F(l, r) for each queries.
N <= 1e6, Q <= 1e6
Thanks!
Wasn't this a codeforces problem? Btw I want to say that while typing this comment I got dejavu
Wow, really cool problem. Source?
Idea is to add up "contribution" from each maximum. For $$$f(l, r)=r-l+1+f(l, m-1)+f(m+1, r)$$$, we consider $$$r-l+1$$$ to be the contribution for $$$m$$$. So, for instance, the maximum in the range $$$[l, m-1]$$$ will contribute $$$(m-1)-l+1$$$ to $$$f(l, r)$$$.
Easy to see that for fixed $$$[l, r]$$$, each index has a fixed and single contribution. Add this up and we are done.
For finding the contribution: let $$$[L[i], R[i]]$$$ be the maximal range in which $$$i$$$ is the maximum. Then not hard to see that the contribution of $$$i$$$ to range $$$[l, r]$$$ is precisely the length of the intersection of its maximal range with the $$$[l, r]$$$ given that $$$i$$$ is in $$$[l, r]$$$ ofc. If you have trouble proving this I can elaborate.
Now finding this efficiently was tricky. Here's what I came up with:
I will describe how to find the contribution of $$$[i, R[i]]$$$, and you can similarly solve it to sum up contribution for $$$[L[i], i-1]$$$.
Maintain a segment tree of size $$$n$$$ initially filled with all zeros. Preprocess: for each $$$i$$$, add $$$1$$$ to $$$[i, R[i]]$$$.
Process the queries in increasing order of $$$l$$$. Now, process all queries with left index $$$l$$$: simply add $$$segtree.sum(l, r)$$$ to the answer of the current query. After you are done with all the queries with left index $$$l$$$, remove $$$1$$$ from $$$[l, R[l]]$$$. We are done!
BTW good job nerd-sniping the community every few weeks.
Observing the form of this contribution, from a different perspective, it is actually the sum of the number of elements in the left and right monotonic stacks for each number in [l, r]. Taking the inquiry offline is a basic scanning line problem that can achieve O((n+q)logn).
CF1117G