[TIOJ] 1603 胖胖殺蚯事件

LINK：https://tioj.infor.org/problems/1603
　　我覺得我差不多沒辦法再拿topcoder了QQ，輸入優化之類的一直爛掉之類的QQ
　　反正還是AC了啦><，就是sparse table套進去~~，但是要注意這題會爆int，但long long我丟會REQQ，所以就是unsigned int啦(但我是看了chino的blog才發現的QQ)

#include<bits/stdc++.h>
using namespace std;
#define int unsigned int
int n,m,l,r;
int ihei[40][100009];
int ahei[40][100009];
inline int rmqi(int a,int b)
{
    int k = __lg(b-a+1);
    return min(ihei[k][a],ihei[k][b-(1<<k)+1]);
}
inline int rmqa(int a,int b)
{
    int k = __lg(b-a+1);
    return max(ahei[k][a],ahei[k][b-(1<<k)+1]);
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> ihei[0][i] , ahei[0][i] = ihei[0][i];
    for(int j = 1; (1<<j) <= n; j++)
        for(int i = 0; i+(1<<j) <= n; i++)
        {   
            ihei[j][i] = min(ihei[j-1][i],ihei[j-1][i+(1<<(j-1))]);
            ahei[j][i] = max(ahei[j-1][i],ahei[j-1][i+(1<<(j-1))]);
        }
    while(m--)
    {
        cin >> l >> r;
        l--; r--;
        cout << rmqa(l,r)-rmqi(l,r) << '\n';
    }
}