# BrainBytes 2

## CP
[Link for the question](https://cses.fi/problemset/task/3304)

We want to know how many buildings from $a$ to $b$ can be covered if we move to the next largest building to our right, Note we will always see the first building $a$ .
Define a function:
$par(x)$ = index of the next largest building to the right of $x-th$ building.
Now we want to find a parent of $x$ such that
$par(par(par...(x)))$ $\le$ $b$.
Lets say, if the $k-th$ par of $x$ is $\le$ b, and the $(k+1)-th$ is $>$ $b$,

the our answer is $k + 1$. Note you would always see the building $x$.
For functions like this, we can use **binary lifting**, and compute ancestors of $x$ in powers of 2.
Thus the question now becomes: what binary ancestor is permissible from some point $a$?
Let's say its $y$, then we repeat the same question for $y$ until we reach the $b-th$ building.
We can calculate the trivials ancestor or the direct parent of $x$ i.e `par(x)` using the stack method to calculate next left/right smallest/largest element.
Here we need to find next largest element to the right for all the buildings.
### Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, q;
    cin >> n >> q;
    vector<ll> h(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    h[n + 1] = LLONG_MAX;
    vector<ll> par(n + 2);
    stack<ll> s;
    for (int i = n; i >= 1; i--)
    {
        while (!s.empty() && h[s.top()] <= h[i])
        {
            s.pop();
        }
        if (s.empty()) par[i] = n + 1;
        else par[i] = s.top();
        s.push(i);
    }
    par[n + 1] = n + 1;
    ll maxc = 25;
    vector<vector<ll>> anc(n + 2, vector<ll>(maxc, LLONG_MAX));
    for (int i = 1; i <= n + 1; i++)
    {
        anc[i][0] = par[i];
    }
    for (int j = 1; j < maxc; j++)
    {
        for (int i = 1; i <= n + 1; i++)
        {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
    while (q--)
    {
        ll a, b;
        cin >> a >> b;
        ll prev = a;
        ll ct = 1;
        for (int j = maxc - 1; j >= 0; j--)
        {
            if (anc[prev][j] <= b)
            {
                prev = anc[prev][j];
                ct += (1LL << j);
            }
        }
        /* 
        for each j, we run once, as to cover the highest possible ancestor from prev, 
        then we are sure we have to move into a lower ancestor,
        thus j required for the new prev would be less
        */
        cout << ct << endl;
    }
}

### Useful Links
[Binary Lifting - CP Algorithms](https://cp-algorithms.com/graph/lca_binary_lifting.html)
[Next Smaller Left](https://www.geeksforgeeks.org/dsa/next-smaller-element/)

## Systems

The Translation Lookaside Buffer (TLB) is the hardware component responsible for caching memory address translations between virtual and physical addresses. In modern computer systems, programs use virtual addresses, which must be translated into physical addresses in RAM. This translation is performed using a page table, which is typically maintained by the operating system.

However, accessing the page table for every memory operation would be inefficient, as it can be slow and involve multiple memory accesses (especially in systems with multi-level page tables). To speed this up, processors include a small, fast cache called the TLB.

The TLB stores recently used virtual-to-physical address mappings. When a memory access is made, the processor first checks the TLB. If the mapping is found (a TLB hit), the translation is immediate. If not (a TLB miss), the system performs a page table lookup and then updates the TLB with the new mapping.

Other options are incorrect:
- Prefetcher is used to predict and load future memory accesses to reduce latency, not for address translation.
- Page Table is the full mapping structure, typically stored in main memory and managed by the OS, not a cache.
- Instruction Decoder translates CPU instructions into control signals but is unrelated to memory address translation.

Therefore, the TLB is the correct answer.

## Puzzle

[Solution Link](https://puzzling.stackexchange.com/questions/29920/a-magic-trick-of-david-copperfield)