1. 奶牛排队

ST表模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const static int MAXN = 200000;
int lg[MAXN];

static void init() {
    lg[0] = -1;
    for (int i = 1; i < MAXN; ++i) {
        lg[i] = lg[i >> 1] + 1;
    }
}

template<int opt(int, int)>
struct ST {

    int u[MAXN][20], n;
    void build(int a[], int n) {
        this->n = n;
        for (int i = 0; i < n; ++i) u[i][0] = a[i];
        for (int j = 1; (1 << j) <= n; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                u[i][j] = opt(u[i][j - 1], u[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int ask(int a, int b) {
        if (a > b) std::swap(a, b);
        int k = lg[b - a + 1];
        return opt(u[a][k], u[b - (1 << k) + 1][k]);
    }
};


const int N = 5e4+10;
int a[N];
int n,q,x,y;

int op1(int x, int y) {return max(x, y);}
int op2(int x, int y) {return min(x, y);}

int main() {
    scanf("%d%d", &n, &q);
    init();
    ST<op1> st1; ST<op2> st2;
    for (int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
    }
    st1.build(a,n); st2.build(a,n);
    for (int i = 0; i < q; i ++ ){
        scanf("%d%d", &x, &y);
        cout << st1.ask(x-1,y-1)-st2.ask(x-1,y-1)<<"\n";
    }

}