rt，不求调，只求分析复杂度是否是 $O(n^2)$……

#include<cstdio>
#include<algorithm>
#include<cassert>
#define ull unsigned long long
using namespace std;
struct poitrans{
	ull mat[5][5];
	friend poitrans operator*(poitrans p1,poitrans p2){
		poitrans p3={{{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}};
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				for(int h=0;h<5;h++){
					p3.mat[i][j]+=p1.mat[i][h]*p2.mat[h][j];
				}
			}
		}
		return p3;
	}
}tra[1049000];
struct poimsg{
	ull len,sa,sb,sab,sans;
	friend poimsg operator*(poimsg p1,poitrans p2){
		return
		{
		p1.len*p2.mat[0][0]+p1.sa*p2.mat[1][0]+p1.sb*p2.mat[2][0]+p1.sab*p2.mat[3][0]+p1.sans*p2.mat[4][0],
		p1.len*p2.mat[0][1]+p1.sa*p2.mat[1][1]+p1.sb*p2.mat[2][1]+p1.sab*p2.mat[3][1]+p1.sans*p2.mat[4][1],
		p1.len*p2.mat[0][2]+p1.sa*p2.mat[1][2]+p1.sb*p2.mat[2][2]+p1.sab*p2.mat[3][2]+p1.sans*p2.mat[4][2],
		p1.len*p2.mat[0][3]+p1.sa*p2.mat[1][3]+p1.sb*p2.mat[2][3]+p1.sab*p2.mat[3][3]+p1.sans*p2.mat[4][3],
		p1.len*p2.mat[0][4]+p1.sa*p2.mat[1][4]+p1.sb*p2.mat[2][4]+p1.sab*p2.mat[3][4]+p1.sans*p2.mat[4][4],
		};
	}
	friend poimsg operator+(poimsg p1,poimsg p2){
		return {p1.len+p2.len,p1.sa+p2.sa,p1.sb+p2.sb,p1.sab+p2.sab,p1.sans+p2.sans};
	}
}seg[1049000]; 
struct qur{
	int l,r,id;
	friend bool operator<(qur q1,qur q2){
		return q1.r<q2.r;
	}
}lx[305416],sta1[305416],sta2[305416];
int t,un=1,n,q,a[256789],b[256789],tp1,tp2;
ull ans[305416];
void psdn(int now){
	if(now<<1>=un*2)return;
	seg[now<<1]=seg[now<<1]*tra[now];
	seg[now<<1|1]=seg[now<<1|1]*tra[now];
	tra[now<<1]=tra[now<<1]*tra[now];
	tra[now<<1|1]=tra[now<<1|1]*tra[now];
	tra[now]={{{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}}}; 
}
void mf(int lb,int rb,ull x,int mode,int now=1,int l=0,int r=un-1){
	if(l>rb||r<lb)return;
	if(l>=lb&&r<=rb){
		switch(mode){
			case 1:{
				seg[now]=seg[now]*(poitrans){{{1,x,0,0,0},{0,0,0,0,0},{0,0,1,x,0},{0,0,0,0,0},{0,0,0,0,1}}};
				tra[now]=tra[now]*(poitrans){{{1,x,0,0,0},{0,0,0,0,0},{0,0,1,x,0},{0,0,0,0,0},{0,0,0,0,1}}};
				break;
			}
			case 2:{
				seg[now]=seg[now]*(poitrans){{{1,0,x,0,0},{0,1,0,x,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,1}}};
				tra[now]=tra[now]*(poitrans){{{1,0,x,0,0},{0,1,0,x,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,1}}};
				break;
			}
			case 3:{
				seg[now]=seg[now]*(poitrans){{{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1},{0,0,0,0,1}}};
				tra[now]=tra[now]*(poitrans){{{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1},{0,0,0,0,1}}};
				break;
			}
		}
		return;
	}
	int mid=(l+r)>>1;
	psdn(now);
	mf(lb,rb,x,mode,now<<1,l,mid);mf(lb,rb,x,mode,now<<1|1,mid+1,r);
	seg[now]=seg[now<<1]+seg[now<<1|1];
}
ull ck(int lb,int rb,int now=1,int l=0,int r=un-1){
	if(l>rb||r<lb)return 0;
	if(l>=lb&&r<=rb){
		return seg[now].sans;
	}
	psdn(now);
	int mid=(l+r)>>1;
	return ck(lb,rb,now<<1,l,mid)+ck(lb,rb,now<<1|1,mid+1,r);
}
void arg(int now=1,int l=0,int r=un-1){
	seg[now].len=r+1-l;
	tra[now]={{{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}}}; 
	if(l==r)return;
	int mid=(l+r)>>1;
	arg(now<<1,l,mid);arg(now<<1|1,mid+1,r);
}
int main(){
	scanf("%d%d",&t,&n);
	while(un<=n)un<<=1;
	arg();
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1;i<=n;i++)scanf("%d",b+i);
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int in1,in2;
		scanf("%d%d",&in1,&in2);
		lx[i]={in1,in2,i};
	}
//	for(int h=1;h<un*2;h++){
//			printf("%d %llu %llu %llu %llu %llu\n",h,seg[h].len,seg[h].sa,seg[h].sb,seg[h].sab,seg[h].sans);
//		}
	sort(lx+1,lx+q+1);
	for(int i=1,j=1;i<=n;i++){
		int l1=i,l2=i;
		while(tp1&&sta1[tp1].id<a[i])l1=sta1[tp1--].l;
		while(tp2&&sta2[tp2].id<b[i])l2=sta2[tp2--].l;
		mf(l1,i,a[i],1);mf(l2,i,b[i],2);mf(1,i,1,3);
//		printf("____i=%d %d %d\n",i,l1,l2);
		while(lx[j].r<=i&&j<=q){
			assert(lx[j].r==i);
			ans[lx[j].id]=ck(lx[j].l,lx[j].r);
			j++;
		}
///		for(int h=1;h<un*2;h++){
//			printf("%d %llu %llu %llu %llu %llu\n",h,seg[h].len,seg[h].sa,seg[h].sb,seg[h].sab,seg[h].sans);
//		}
		sta1[++tp1]={l1,i,a[i]};sta2[++tp2]={l2,i,b[i]};
	}
	for(int i=1;i<=q;i++)printf("%llu\n",ans[i]);
}
/*
5 5
1 2 3 4 5
5 4 3 2 1
10
1 2 2 3 3 4 4 5
1 3 2 4 3 5
1 4 2 5
1 5
*/