| # | 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 | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
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