开个坑先。
此题解包含所有部分分以及大部分正解的做法，望周知。
题目大意：
给定两个长度为 $n$ 的排列 $a$，$b$，每次询问给定区间 $[l,r]$ 求：
$$
\sum_{p=l}^r\sum_{q=p}^r \max_{i=p}^q a_i\times \max_{i=p}^q b_i
$$
即两个排列的所有子区间最大值的乘积之和。
$O(qn^2)$ 暴力：
对于每次询问，枚举所有子区间，对每个子区间递推求出其最大值（边枚举区间边在区间扩张时更新最大值）。
预期得分：8pts。
$O(n^2+q)$ 暴力：
设 $f_{i,j}$ 表示区间右端点为 $j$，左端点为 $[i,j]$ 所有区间的最大值乘积之和，则满足递推关系 $f_{i,j}=f_{i+1,j}+\max_{k=i}^j a_i \times \max_{k=i}^j b_i$，设 $ans_{l,r}$ 为答案，满足递推关系 $ans_{l,r}=ans_{l,r-1}+f_{l,r}$，即可在 $O(n^2)$ 时间内求出所有答案。
预期得分：20pts。
$O(qn\log n)$ 单调栈+倍增+对每项询问 dp。
首先用单调栈对每个位置预处理出比当前位置大的最大位置。
预期得分：52pts。
O(qn\log n)：分治。
随机化1：$a_i$，$b_i$ 随机。
对最大值分治。
预期得分：32pts。
将以上所有部分分拼起来即可得到 76pts 的高分，这也是一个 NOIP 选手应该在赛场上拿到的分（前提是你的码力比较强）。
随机化2：$a_i$ 随机。
预期得分：52pts。
莫队。
预期得分：52pts。
将以上所有部分分拼起来即可得到 92pts 的高分（谁还打正解(bushi)）。
正解1：历史最值线段树。
#include<bits/stdc++.h>
#define int unsigned long long
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int N=2.5e5+5;
int CASE,n,q,st[N],r;
int sa[N],sb[N],sab[N],ans[N];
int a[N],b[N],la[N][20],lb[N][20];
struct node{int l,r,id;};
vector<node>R[N];
struct Segment_Tree{
#define mid (l+(r-l>>1))
#define ls (mid<<1)
#define rs (ls|1)
int L,R,K;
struct D{int sxy,sx,sy,s,len;}info[N<<1];
struct M{int cx,cy,mxy,mx,my,m;bool et;}tag[N<<1];
inline D pushup(D lst,D rst){
D now;
now.sxy=lst.sxy+rst.sxy;
now.sx=lst.sx+rst.sx;
now.sy=lst.sy+rst.sy;
now.s=lst.s+rst.s;
return now;
}
inline D chgD(M now,D st){
st.s+=now.mxy*st.sxy+now.mx*st.sx+now.my*st.sy+now.m*st.len;
if(now.cx&&now.cy){
st.sxy=st.len*now.cx*now.cy;
st.sx=st.len*now.cx;
st.sy=st.len*now.cy;
}else if(now.cx){
st.sxy=st.len*now.cx*st.sy;
st.sx=st.len*now.cx;
}
else if(now.cy){
st.sxy=st.len*st.sx*now.cy;
st.sy=st.len*now.cy;
}
return st;
}
inline M chgM(M now,M st){
if(st.cx&&st.cy)st.m+=now.mxy*st.cx*st.cy+now.mx*st.cx+now.my*st.cy+now.m;
else if(st.cx){
st.m+=now.mx*st.cx+now.m;
st.my+=now.my+now.mx*st.cx;
}else if(st.cy){
st.m+=now.my*st.cy+now.m;
st.mx+=now.mx+now.my*st.cy;
}else{
st.m+=now.m;
st.mx+=now.mx;
st.my+=now.my;
st.mxy+=now.mxy;
}
st.cx=now.cx;
st.cy=now.cy;
return st;
}
inline void pushdown(int l,int r,int id){
if(!tag[id].et){
info[ls]=chgD(tag[id],info[ls]);
info[ls]=chgD(tag[id],info[rs]);
tag[ls]=chgM(tag[id],tag[ls]);
tag[ls]=chgM(tag[id],tag[rs]);
tag[id].et=0;
}
}
inline void upda(int l,int r,int id){
if(L<=mid&&mid<R)
{info[id]=chgD({K,0,0,0,0,0},info[id]);return;}
pushdown(l,r,id);
upda(l,mid,ls),upda(mid+1,r,rs);
}
inline void updb(int l,int r,int id){
if(L<=mid&&mid<R)
{info[id]=chgD({0,K,0,0,0,0},info[id]);return;}
pushdown(l,r,id);
updb(l,mid,ls),updb(mid+1,r,rs);
info[id]=pushup(info[ls],info[rs]);
}
inline D qry(int l,int r,int id){
if(L<=l&&r<=R)return info[id];
pushdown(l,r,id);
if(L<=mid&&mid<R)return pushup(qry(l,mid,ls),qry(mid+1,r,rs));
return (L<=mid?qry(l,mid,ls):qry(mid+1,r,rs));
}
}Tr;
signed main(){
// freopen("std.in","r",stdin);
// freopen("mine.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>CASE>>n;
for(int i=1; i<=n; ++i){
cin>>a[i];
while(r&&a[st[r]]<=a[i])--r;
la[i][0]=st[r];st[++r]=i;
}r=0;
for(int i=1; i<=n; ++i){
cin>>b[i];
while(r&&b[st[r]]<=b[i])--r;
lb[i][0]=st[r];st[++r]=i;
}
for(int i=1; i<=n; ++i)
for(int j=1; j<20; ++j)
la[i][j]=la[la[i][j-1]][j-1],
lb[i][j]=lb[lb[i][j-1]][j-1];
cin>>q;int l,r,res;
for(int r=1; r<=n; ++r){
Tr.L=la[r][0]+1,Tr.R=r,Tr.K=a[r],Tr.upda(1,n,1);
Tr.L=lb[r][0]+1,Tr.R=r,Tr.K=b[r],Tr.updb(1,n,1);
for(node j:R[r]){
ans[R[r].id]=Tr.qry(r)-Tr.qry(R[r].l-1);
}
}
for(int i=1; i<=q; ++i)
cout<<ans[i]<<'\n';
return 0;
}
