我这个矩乘能跑88分,好像其他都是76,而且在loj是可以通过全部数据的,不知道可不可以再优化,实在不行我就换写法吧

#include<bits/stdc++.h>
using namespace std;
const int N=2.5e5+5;
typedef unsigned long long ull;
namespace fast_IO{
    #define FASTIO
    #define IOSIZE 100000
    char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
    #define getchar()((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
    #define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #define isdigit(ch)(ch>47&&ch<58)
    #define isspace(ch)(ch<33)
    template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}
    #ifdef _GLIBCXX_STRING
    inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}
    #endif
    template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a);print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
}using namespace fast_IO;
struct Matrix{
	ull a[5][5];
	int n,m;
	inline void SetSz(int n1,int m1){
		n=n1,m=m1;
	}
	inline void Set(){
		memset(a,0,sizeof(a));
		for(int i=0;i<5;i++)a[i][i]=1;
	}
	Matrix operator * (const Matrix & b)const {
		Matrix c;
		c.SetSz(n,b.m);
		for(int i=0;i<n;i++)
			for(int j=0;j<b.m;j++){
				c.a[i][j]=0;
				for(int k=0;k<m;k++)
					c.a[i][j]+=a[i][k]*b.a[k][j];				
			}
		return c;
	}
	Matrix operator + (const Matrix & b)const {
		Matrix c;
		c.SetSz(5,1);
		for(int i=0;i<5;i++)c.a[i][0]=a[i][0]+b.a[i][0];
		return c;
	}
};
struct segment{
	Matrix val;
	Matrix mod;
	bool bj;
}seg[N<<2];
int Rt=1;
#define ls rt<<1
#define rs rt<<1|1
inline void pushup(int rt){
	seg[rt].val=seg[ls].val+seg[rs].val;
}
inline void pushmod(int rt,Matrix &mod){
	seg[rt].val=mod*seg[rt].val;
	seg[rt].mod=mod*seg[rt].mod;
	seg[rt].bj=1;
}
inline void pushdown(int rt){
	if(seg[rt].bj){
		pushmod(ls,seg[rt].mod);
		pushmod(rs,seg[rt].mod);
		seg[rt].mod.Set();		
		seg[rt].bj=0;
	}
}
void Build(int rt,int l,int r){
	if(l>r)return;
	memset(seg[rt].mod.a,0,sizeof(seg[rt].mod.a));
	memset(seg[rt].val.a,0,sizeof(seg[rt].val.a));
	seg[rt].bj=0;
	seg[rt].mod.SetSz(5,5);
	seg[rt].val.SetSz(5,1);
	
	seg[rt].mod.Set();
	seg[rt].val.a[4][0]=r-l+1;
	if(l==r)return;
	int mid=l+r>>1;
	Build(ls,l,mid);
	Build(rs,mid+1,r);
}
Matrix mul;
void Modify(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R){pushmod(rt,mul);return;}
	int mid=l+r>>1;
	pushdown(rt);
	if(L<=mid)Modify(ls,l,mid,L,R);
	if(R>mid)Modify(rs,mid+1,r,L,R);
	pushup(rt);
}
ull Ask(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R)return seg[rt].val.a[3][0];
	int mid=l+r>>1;
	pushdown(rt);
	ull now=0;
	if(L<=mid)now+=Ask(ls,l,mid,L,R);
	if(R>mid)now+=Ask(rs,mid+1,r,L,R);
	return now;
}

int ID,n,m;
int a[N],b[N],stk1[N],stk2[N],top1,top2;
ull ans[N];
struct query{
	int l,r,id;
	bool operator < (const query & b)const {
		if(r==b.r)return l>b.l;
		return r<b.r;
	}
}q[N];
int main(){
//	freopen("match25.in","r",stdin);
//	freopen("match.out","w",stdout);
	
//	double s=clock();
	io>>ID>>n;
	for(int i=1;i<=n;i++)io>>a[i];
	for(int i=1;i<=n;i++)io>>b[i];
	io>>m;
	for(int i=1;i<=m;i++)io>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+1+m);
	Build(Rt,1,n);
	
//	double t=clock();
//	cerr<<"initial: "<<(t-s)<<'\n';
	
	int p=1;
	
	mul.SetSz(5,5); 
	for(int i=1;i<=n;i++){
		if(p>m)break;
		
		int l1=0,l2=0;
		while(top1&&a[stk1[top1]]<a[i])--top1;
		l1=stk1[top1]+1;	
		stk1[++top1]=i;		
		
		while(top2&&b[stk2[top2]]<b[i])--top2;
		l2=stk2[top2]+1;
		stk2[++top2]=i;	
		
		memset(mul.a,0,sizeof(mul.a));		
		mul.a[0][4]=a[i],mul.a[1][4]=b[i],mul.a[2][4]=1ull*a[i]*b[i];
		mul.a[3][3]=mul.a[4][4]=1;
		Modify(Rt,1,n,max(l1,l2),i);
		
		memset(mul.a,0,sizeof(mul.a));
		mul.a[3][3]=mul.a[4][4]=1;
		if(l1<l2)mul.a[0][4]=a[i],mul.a[1][1]=1,mul.a[2][1]=a[i];
		if(l2<l1)mul.a[0][0]=1,mul.a[1][4]=b[i],mul.a[2][0]=b[i];
		
		if(l1!=l2)Modify(Rt,1,n,min(l1,l2),max(l1,l2)-1);
		
		mul.Set();
		mul.a[3][2]=1;
		Modify(Rt,1,n,1,i);
		
		ull now=0,last=i;
		while(p<=m&&q[p].r<=i){
			if(q[p].l<=last)now+=Ask(Rt,1,n,q[p].l,last);
			ans[q[p].id]=now;
			last=q[p].l-1;
			++p;
		}
	}
	for(int i=1;i<=m;i++)io<<ans[i]<<'\n';
	return 0;
}