| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3898 |
| 2 | tourist | 3840 |
| 3 | orzdevinwang | 3706 |
| 4 | ksun48 | 3691 |
| 5 | jqdai0815 | 3682 |
| 6 | ecnerwala | 3525 |
| 7 | gamegame | 3477 |
| 8 | Benq | 3468 |
| 9 | Ormlis | 3381 |
| 10 | maroonrk | 3379 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 168 |
| 2 | -is-this-fft- | 165 |
| 3 | Dominater069 | 160 |
| 3 | Um_nik | 160 |
| 5 | atcoder_official | 159 |
| 6 | djm03178 | 157 |
| 7 | adamant | 153 |
| 8 | luogu_official | 150 |
| 9 | awoo | 149 |
| 10 | TheScrasse | 146 |
lets say we have an array a of length n.
we are given q queries with indices l,r.
we have to locate the position of minimum or maximum value within that range....of l,r.
the constraints are
.........1<=n<=10^5 .........1<=l<=r<=n .........1<=ai<=10^9 .........1<=q<=10^5
You can do it by preparing a 2D array
xwherex[k][i]is the minimum/maximum value in range $$$[i,i+2^k-1]$$$.x[0][i]=a[i]and for each $$$k\geq1$$$,x[k][i]=min(x[k-1][i],x[k-1][i+(1ll<<(k-1)]). The complexity is $$$O(n\log n)$$$, since $$$k\leq\log n$$$, $$$i<n$$$ and eachx[k][i]can be calculated in $$$O(1)$$$ time.Then, to calculate the minimum/maximum value of the range $$$[l,r]$$$, calculate the largest number $$$y$$$ such that $$$2^y\leq r-l+1$$$. The answer is
min(x[y][l],x[y][r-(1ll<<y)]).To also find the index of that element, simply use this technique on an array of pairs
b[n], whereb[i]={a[i],i}.at that point, just use segtree
everytime you merge two node, you merge val and index(updating val to min/max and index to new min/max)
That's what I'd do if I had to solve this, but I think what I described might be more simple. Although the way segment trees work is easier to understand, the implementation is a bit tricky, so I wouldn't recommend using a segment tree for this problem if it's the first time you use one.
true
false, $$$O(nq)$$$ is much simplier to understand and implement.
O(qn)May lead to TLE
It can't if you write cache-efficient code.
You can do it offline with ordered stack
This is dp ...