Code: A Simple Problem

#include <bits/stdc++.h>

#define int long long

template <typename T> struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n = 0) { init(n); }

    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }

    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }

    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) { return sum(r) - sum(l); }

    int kth(T k) {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

struct c {
    int c0 = 0, c1 = 0, c2 = 0, t0 = 0, t1 = 0;

    c operator+(const c &o) const {
        return {c0 + o.c0, c1 + o.c1, c2 + o.c2, t0 + o.t0, t1 + o.t1};
    }
    c operator-(const c &o) const {
        return {c0 - o.c0, c1 - o.c1, c2 - o.c2, t0 - o.t0, t1 - o.t1};
    }
    c &operator+=(const c &o) {
        c0 += o.c0;
        c1 += o.c1;
        c2 += o.c2;
        t0 += o.t0;
        t1 += o.t1;
        return *this;
    }

    int re(int l) const {
        return c0 + c1 * l + c2 * l * l - ((l % 2 != 0) ? t0 : t1);
    }
};

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> p(n + 1), nxt(n + 2, n + 1), st;

    for (int i = 1; i <= n; ++i) {
        std::cin >> p[i];
        while (!st.empty() && p[st.back()] > p[i]) {
            nxt[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }

    std::vector<std::vector<int>> adj(n + 2),
        up(n + 2, std::vector<int>(20, n + 1)), temp(n + 2);

    for (int i = 1; i <= n; ++i) {
        adj[nxt[i]].push_back(i);
    }

    std::vector<int> ti(n + 2), to(n + 2);
    int cnt = 0;

    auto dfs = [&](auto &self, int u) -> void {
        ti[u] = cnt++;
        for (int i = 1; i < 20; ++i) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
        for (int v : adj[u]) {
            up[v][0] = u;
            self(self, v);
        }
        to[u] = cnt;
    };

    dfs(dfs, n + 1);

    std::vector<std::vector<std::pair<int, int>>> q(n + 1);

    for (int i = 0; i < m; ++i) {
        int l, r;
        std::cin >> l >> r;
        q[l].push_back({r, i});
    }

    auto get = [](int x) -> int { return (x * x) / 4; };

    auto get1 = [](int x, int y) -> c {
        int t = y - x;
        return {4 * t * y - 4 * t * t, -4 * t, 0, 0, 0};
    };

    auto get2 = [](int y) -> c {
        return {y * y, -2 * y, 1, (y % 2 == 0 ? 1 : 0), (y % 2 != 0 ? 1 : 0)};
    };

    Fenwick<c> f(n + 5);

    for (int i = 1; i <= n; ++i) {
        c t2 = get2(nxt[i]);
        f.add(ti[i], t2);
        f.add(to[i], c() - t2);

        int mi = 2 * i - nxt[i] - 1;
        if (mi > 0) {
            temp[std::min(n, mi)].push_back(i);
        }
    }

    std::vector<int> ans(m);

    for (int i = n; i >= 1; --i) {

        for (int x : temp[i]) {
            c t = get1(x, nxt[x]) - get2(nxt[x]);
            f.add(ti[x], t);
            f.add(to[x], c() - t);
        }

        for (auto [fi, se] : q[i]) {
            if (i == fi) {
                ans[se] = 0;
                continue;
            }

            int u2 = up[i][0];

            if (u2 > fi) {
                ans[se] = get(fi - i);
                continue;
            }

            int tc = i;

            for (int j = 19; j >= 0; --j) {
                if (up[tc][j] <= fi) {
                    tc = up[tc][j];
                }
            }

            c ts = f.sum(ti[i] + 1) - f.sum(ti[tc] + 1);
            int s = ts.re(i) / 4;

            int t1 = fi + 1 - tc;
            int t2 = fi + 1 - i;
            int t3 = 0;

            if (t2 <= 2 * t1) {
                t3 = get(t2);
            } else {
                t3 = t1 * (t2 - t1);
            }

            ans[se] = s + t3 - get(u2 - i) + get(u2 - i - 1);
        }
    }

    for (int i = 0; i < m; ++i) {
        std::cout << ans[i] << "\n";
    }
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    int _ = 1;
    std::cin >> _;

    while (_--) {
        solve();
    }

    return 0;
}