常规分块做法TLE，64求调

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int MAXN = 500005;
int A[MAXN], B[MAXN], n, q, kuai;
ull AA[MAXN], BB[MAXN], CC[MAXN], lans[MAXN];
struct qua { int l, r, bh; } quary[MAXN];
struct prt { int l, r; ull Asame, Bsame, Csum, Cadd; } fk[MAXN];

inline bool cmp(qua a, qua b) { return a.r < b.r; }
inline bool cmp2(qua a, qua b) { return a.bh < b.bh; }

int gk(int x) { return (x - 1) / kuai + 1; }

inline void skA(int l, int r, int c) {
    int bl = gk(l);
    if (fk[bl].l == l && fk[bl].r == r) {
        fk[bl].Asame = c;
    } else {
        if (fk[bl].Asame != 0) {
            for (int i = fk[bl].l; i <= fk[bl].r; i++)
                AA[i] = fk[bl].Asame;
        }
        fk[bl].Asame = 0;
        for (int i = l; i <= r; i++) AA[i] = c;
    }
}

inline void pushA(int l, int r, int c) {
    if (gk(l) == gk(r)) {
        skA(l, r, c);
        return;
    }
    skA(l, fk[gk(l)].r, c);
    skA(fk[gk(r)].l, r, c);
    for (int i = gk(l) + 1; i < gk(r); i++)
        fk[i].Asame = c;
}

inline void skB(int l, int r, int c) {
    int bl = gk(l);
    if (fk[bl].l == l && fk[bl].r == r) {
        fk[bl].Bsame = c;
    } else {
        if (fk[bl].Bsame != 0) {
            for (int i = fk[bl].l; i <= fk[bl].r; i++)
                BB[i] = fk[bl].Bsame;
        }
        fk[bl].Bsame = 0;
        for (int i = l; i <= r; i++) BB[i] = c;
    }
}

inline void pushB(int l, int r, int c) {
    if (gk(l) == gk(r)) {
        skB(l, r, c);
        return;
    }
    skB(l, fk[gk(l)].r, c);
    skB(fk[gk(r)].l, r, c);
    for (int i = gk(l) + 1; i < gk(r); i++)
        fk[i].Bsame = c;
}

inline void skC(int l, int r) {
    int i = gk(l);
    if (fk[i].Asame != 0 && fk[i].Bsame != 0) {
        for (int j = l; j <= r; j++)
            CC[j] += fk[i].Asame * fk[i].Bsame, fk[i].Csum += fk[i].Asame * fk[i].Bsame;
    } else if (fk[i].Asame == 0 && fk[i].Bsame != 0) {
        for (int j = l; j <= r; j++)
            CC[j] += AA[j] * fk[i].Bsame, fk[i].Csum += AA[j] * fk[i].Bsame;
    } else if (fk[i].Asame != 0 && fk[i].Bsame == 0) {
        for (int j = l; j <= r; j++)
            CC[j] += fk[i].Asame * BB[j], fk[i].Csum += fk[i].Asame * BB[j];
    } else {
        for (int j = l; j <= r; j++)
            CC[j] += AA[j] * BB[j], fk[i].Csum += AA[j] * BB[j];
    }
}

inline void pushC(int l, int r) {
    if (gk(l) == gk(r)) {
        skC(l, r);
        return;
    }
    skC(l, fk[gk(l)].r);
    skC(fk[gk(r)].l, r);
    for (int i = gk(l) + 1; i < gk(r); i++) {
        if (fk[i].Asame != 0 && fk[i].Bsame != 0) {
            fk[i].Cadd += fk[i].Asame * fk[i].Bsame;
            fk[i].Csum += fk[i].Asame * fk[i].Bsame * (fk[i].r - fk[i].l + 1);
        } else if (fk[i].Asame == 0 && fk[i].Bsame != 0) {
            for (int j = fk[i].l; j <= fk[i].r; j++)
                CC[j] += AA[j] * fk[i].Bsame, fk[i].Csum += AA[j] * fk[i].Bsame;
        } else if (fk[i].Asame != 0 && fk[i].Bsame == 0) {
            for (int j = fk[i].l; j <= fk[i].r; j++)
                CC[j] += fk[i].Asame * BB[j], fk[i].Csum += fk[i].Asame * BB[j];
        } else {
            for (int j = fk[i].l; j <= fk[i].r; j++)
                CC[j] += AA[j] * BB[j], fk[i].Csum += AA[j] * BB[j];
        }
    }
}

inline ull skask(int l, int r) {
    ull ans = 0;
    for (int i = l; i <= r; i++)
        ans += CC[i] + fk[gk(l)].Cadd;
    return ans;
}

inline ull askC(int l, int r) {
    if (gk(l) == gk(r)) return skask(l, r);
    ull ans = skask(l, fk[gk(l)].r) + skask(fk[gk(r)].l, r);
    for (int i = gk(l) + 1; i < gk(r); i++)
        ans += fk[i].Csum;
    return ans;
}

signed main() {
	ios::sync_with_stdio(false);
    cin >> n; cin >> n; kuai = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int j = 1; j <= n; j++) cin >> B[j];
    cin >> q;
    for (int i = 1; i <= q; i++) cin >> quary[i].l >> quary[i].r;
    for (int i = 1; i <= q; i++) quary[i].bh = i;
    sort(quary + 1, quary + q + 1, cmp);
    stack<int> s1, s2;
    int gt = 1;
    for (int i = 1; i <= ceil(n / (double)kuai); i++)
        fk[i].l = kuai * (i - 1) + 1, fk[i].r = min(n, kuai * i);
    for (int i = 1; i <= n; i++) {
        while (s1.size() && A[s1.top()] < A[i]) s1.pop();
        while (s2.size() && B[s2.top()] < B[i]) s2.pop();
        int x1, x2;
        if (s1.size()) x1 = s1.top();
        else x1 = 0;
        if (s2.size()) x2 = s2.top();
        else x2 = 0;
        s1.push(i);
        s2.push(i);
        pushA(x1 + 1, i, A[i]);
        pushB(x2 + 1, i, B[i]);
        pushC(1, i);
        for (; gt <= q && quary[gt].r == i; gt++)
            lans[quary[gt].bh] = askC(quary[gt].l, quary[gt].r);
    }
    for (int i = 1; i <= q; i++) cout << lans[i] << endl;
    return 0;
}