| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 145 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 7 | nik_exists | 133 |
| 9 | AmShZ | 130 |
| 10 | Dominater069 | 129 |
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 \lt 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