| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 162 |
| 3 | adamant | 161 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 151 |
| 6 | nor | 150 |
| 7 | atcoder_official | 147 |
| 7 | SecondThread | 147 |
| 9 | TheScrasse | 146 |
| 10 | Petr | 145 |
https://www.spoj.com/problems/ONEXLIS/
i have been trying to solve the problem for a long time...but couldnt come up with a proper approach... My approach(ig wrong) : when we consider a sequence to be lis, the elements before the last element must have lds(longest strictly decreasing subsequence) > 1; however im unable to implement the idea; any help would be appreciated.
Auto comment: topic has been updated by Whimsical_HITMAN (previous revision, new revision, compare).
Firstly without loss of generality, we can assume that $$$0 \le a_i \le n - 1$$$, by coordinate compression.
Let's try fixing the one pair that is out of order in the subsequence. Define $$$l_x, r_x$$$ to be the longest increasing sequence ending at index $$$x$$$ and the longest increasing sequence starting from index $$$y$$$ respectively. These values can be computed for all $$$x$$$ using a segment tree in one pass. Then the answer to the problem is $$$\max_{i < j, a[i] > a[j]} l_i + r_j$$$. Iterating over $$$j$$$, this is also doable using a segment tree.
iterating over all j will give tle right?
For every $$$j$$$ you do $$$O(\log n)$$$ work, so it should not.