1.倍增

#include <iostream>

const int N = 100000 + 5000;
const int M = 21;

int a[N];
int t[N];

int n;

int f[N][M];//从第i站转车2的j次方到的站
int g[N][M];//从第i站专车2的j次方到的站用的时间

void init()
{
    for (int i = 1 ; i <= n ; i ++)
    {
        f[i][0] = a[i];
        g[i][0] = t[i];
    }//2的0次方 
    for (int i = 1 ; i <= 20; i ++)
    {
        for (int j = 1 ; j <= n ; j ++)
        {
            f[j][i] = f[f[j][i - 1]][i - 1];//先跳一半,再跳一半 
            g[j][i] = g[j][i - 1] + g[f[j][i - 1]][i - 1];//前一段的时间加上后一段 
        }
    }
}

void solve()
{
    int m;
    std :: cin >> m;
    int r = 1;//从1号站出发
    int time = 0;//时间
    for (int i = 20; i >= 0 ; i --)//移动2的i次方站 
    {
        if ((1 << i) <= m)
        {
            time += g[r][i];//从r出发移动2的j次方站所用的时间 
            r = f[r][i];//从r出发移动2的i次方站
            m -= (1 << i);//移动
            if (m == 0) break;//完了 
        }
    }
    std :: cout << r << " " << time << "\n";
}

int main()
{
    std :: cin >> n;
    for (int i = 1 ; i <= n ; i ++)
    {
        std :: cin >> a[i] >> t[i];
    }
    int m;
    std :: cin >> m;
    init();//初始化 
    while (m --) solve();
}

### 区间最大值和最小值

```cpp
#include 

const int N = 100005;

int h[N];
int n;

int f[N][21];//从i开始2的j次方个数最大值
int g[N][21];//从i开始2的j次方个数最小值
int lg[N];

void init()
{
    for (int i = 1 ; i <= n ; i ++) 
    {
        f[i][0] = h[i];
        g[i][0] = h[i];
    }
    for (int i = 1 ; i <= 20 ; i ++)
    {
        for (int j = 1 ; j + (1 << i) -1 <= n; j ++)
        {
            f[j][i] = std :: max(f[j][i - 1],f[j + (1 << (i - 1))][i - 1]);
            g[j][i] = std :: min(g[j][i - 1],g[j + (1 << (i - 1))][i - 1]);
        }
    }
    lg[1] = 0;
    for (int i = 2 ; i <= n ; i ++)
    {
        lg[i] = lg[i / 2] + 1;
    }
}

int querymax(int l,int r)
{
    int s = lg[r - l + 1];
    return std :: max(f[l][s],f[r-(1 << s) + 1][s]);
}

int querymin(int l,int r)
{
    int s = lg[r - l + 1];
    return std :: min(g[l][s],g[r-(1 << s) + 1][s]);
}

void solve()
{
    int l,r;
    std :: cin >> l >> r;
    int ans = querymax(l,r) - querymin(l,r);
    std :: cout << ans << "\n";
    //std :: cout <<  querymax(l,r) << " " << querymin(l,r) << "\n";
}

int main()
{   int t;
    std :: cin >> n;
    std :: cin >> t;
    for (int i = 1 ; i <= n ; i ++)
    {
        std :: cin >> h[i];
    }
    init();

    while (t --)solve();
}