做法就是扫描线转化成区间加历史最大值乘积和。

为什么我写的暴力矩乘都不对，感觉贡献矩阵也没写错啊。

#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef unsigned long long ll;
il int read(){
    int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-48,c=getchar();
    return x;
}
const int N=2.5e5+5,M=5;
int sid,n,m,a[N],b[N];
struct TAG{
    ll a[M][M];
    il TAG(){memset(a,0,sizeof(a));}
    friend TAG operator*(const TAG &a,const TAG &b) {
        TAG c;for(int i=0;i<M;++i) for(int j=0;j<M;++j) c.a[i][j]=0;
        for(int i=0;i<M;++i)
            for(int k=0;k<M;++k)
                for(int j=0;j<M;++j) c.a[i][j]+=a.a[i][k]*b.a[k][j];
        return c;
    }
}tag[N<<2],A,ONE;int ck[N<<2];
il TAG INIT(){
    TAG a;for(int i=0;i<M;++i) for(int j=0;j<M;++j) a.a[i][j]=(i==j);
    return a;
}
il TAG makeA(){
    TAG a;for(int i=0;i<M;++i) for(int j=0;j<M;++j) a.a[i][j]=(i==j);
    a.a[4][3]=1;return a;
}
il TAG adda(ll w){
    TAG a;for(int i=0;i<M;++i) for(int j=0;j<M;++j) a.a[i][j]=(i==j);
    a.a[0][2]=a.a[3][1]=w;return a;
}
il TAG addb(ll w){
    TAG a;for(int i=0;i<M;++i) for(int j=0;j<M;++j) a.a[i][j]=(i==j);
    a.a[1][2]=a.a[3][0]=w;return a;
}
struct node{
    ll a[M];
    il node(){a[0]=a[1]=a[2]=a[3]=a[4]=0;}
    friend node operator+(const node &a,const node &b) {
        node c;for(int i=0;i<M;++i) c.a[i]=a.a[i]+b.a[i];
        return c;
    }
    friend node operator*(const TAG &a,const node &b){
        node c;for(int i=0;i<M;++i) c.a[i]=0;
        for(int i=0;i<M;++i) for(int j=0;j<M;++j) c.a[i]+=a.a[i][j]*b.a[j];
        return c;
    }
}t[N<<2];
il void pushup(int x){t[x]=t[x<<1]+t[x<<1|1];}
il void maketag(int x,TAG w){t[x]=w*t[x],tag[x]=w*tag[x],ck[x]=1;}
il void pushdown(int x){
    if(!ck[x]) return ;
    maketag(x<<1,tag[x]),maketag(x<<1|1,tag[x]),tag[x]=ONE;
}
void build(int x,int l,int r){
    tag[x]=ONE;
    if(l==r){t[x].a[0]=a[l],t[x].a[1]=b[l],t[x].a[2]=1,t[x].a[3]=1ull*a[l]*b[l],t[x].a[4]=0;return ;}
    int mid=(l+r)>>1;build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    pushup(x);
}
void update(int x,int l,int r,int L,int R,ll w,int type){
    if(l>=L && r<=R){
        if(type==1) maketag(x,adda(w));
        else maketag(x,addb(w));
        return ;
    }
    int mid=(l+r)>>1;pushdown(x);
    if(L<=mid) update(x<<1,l,mid,L,R,w,type);
    if(R>mid) update(x<<1|1,mid+1,r,L,R,w,type);
    pushup(x);
}
void update1(int x,int l,int r,int L,int R){
    if(l>=L && r<=R){
        maketag(x,A);
        return ;
    }
    int mid=(l+r)>>1;pushdown(x);
    if(L<=mid) update1(x<<1,l,mid,L,R);
    if(R>mid) update1(x<<1|1,mid+1,r,L,R);
    pushup(x);
}
node query(int x,int l,int r,int L,int R){
    if(l>=L && r<=R) return t[x];
    int mid=(l+r)>>1;pushdown(x);
    if(L>mid) return query(x<<1|1,mid+1,r,L,R);
    else if(R<=mid) return query(x<<1,l,mid,L,R);
    else return query(x<<1,l,mid,L,R)+query(x<<1|1,mid+1,r,L,R);
}
int st1[N],t1,st2[N],t2;
vector<pii> e[N];ll ans[N];
int opt,l,r,x,y,z,u,v,w;char c;
int main(){
    //freopen("match2.in","r",stdin);
    //freopen("match2.out","w",stdout);
    scanf("%d%d",&sid,&n);A=makeA(),ONE=INIT();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i) b[i]=read();
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;++i) x=read(),y=read(),e[y].push_back({x,i});
    for(int i=1;i<=n;++i){
        while(t1 && a[st1[t1]]<a[i]) update(1,1,n,st1[t1-1]+1,st1[t1],a[i]-a[st1[t1]],1),--t1;
        //update(1,1,n,i,i,a[i],1);
        st1[++t1]=a[i];
        while(t2 && b[st2[t2]]<b[i]) update(1,1,n,st2[t2-1]+1,st2[t2],b[i]-b[st2[t2]],2),--t2;
        //update(1,1,n,i,i,b[i],2);
        st2[++t2]=b[i];
        update1(1,1,n,1,i);
        for(auto it:e[i]) ans[it.se]=query(1,1,n,it.fi,i).a[4];
    }
    for(int i=1;i<=m;++i) printf("%llu\n",ans[i]);
    return 0;
}
/*
0 4
3 1 4 2
2 3 1 4
1
1 4
*/