RT

样例过不去，但是真的查不出来错

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=5e5+5;
ll T,n,q;
ll a[MAXN],b[MAXN];
struct node{
	ll l,r,id;
	bool operator < (const node &oth)const{
		return r<oth.r;
	}
}t[MAXN];
ll st_a[MAXN],top_a,st_b[MAXN],top_b;
struct sgm_t{
	ull ans[MAXN<<2],sum[MAXN<<2],sum_a[MAXN<<2],sum_b[MAXN<<2],lazy_a[MAXN<<2],lazy_b[MAXN<<2],lazy_time[MAXN<<2];
	void push_up(ll id){
		ans[id]=ans[id<<1]+ans[id<<1|1];
		sum[id]=sum[id<<1]+sum[id<<1|1];
		return;
	}
	void add_a(ll id,ll L,ll R,ll delta){
		sum[id]+=delta*sum_b[id];
		sum_a[id]+=(R-L+1)*delta;
		lazy_a[id]+=delta;
		return;
	}
	void add_b(ll id,ll L,ll R,ll delta){
		sum[id]+=delta*sum_a[id];
		sum_b[id]+=(R-L+1)*delta;
		lazy_b[id]+=delta;
		return;
	}
	void add_time(ll id,ll L,ll R,ll delta){
		ans[id]+=delta*sum[id];
		lazy_time[id]+=delta;
		return;
	}
	void push_down(ll id,ll L,ll R){
		ll mid=(L+R)>>1;
		if(lazy_a[id]){
			add_a(id<<1,L,mid,lazy_a[id]);
			add_a(id<<1|1,mid+1,R,lazy_a[id]);
			lazy_a[id]=0;
		}
		if(lazy_b[id]){
			add_b(id<<1,L,mid,lazy_b[id]);
			add_b(id<<1|1,mid+1,R,lazy_b[id]);
			lazy_b[id]=0;
		}
		if(lazy_time[id]){
			add_time(id<<1,L,mid,lazy_time[id]);
			add_time(id<<1|1,mid+1,R,lazy_time[id]);
			lazy_time[id]=0;
		}
		return;
	}
	void build(ll id,ll L,ll R){
		if(L>R)return;
		if(L==R){
			sum_a[id]=a[L];
			sum_b[id]=b[L];
			sum[id]=a[L]*b[L];
			return;
		}
		ll mid=(L+R)>>1;
		build(id<<1,L,mid);
		build(id<<1|1,mid+1,R);
		push_up(id);
		return;
	}
	void update_a(ll id,ll L,ll R,ll UL,ll UR,ll delta){
		if(L>R||UR<L||R<UL)return;
		if(UL<=L&&R<=UR){
			add_a(id,L,R,delta);
			return;
		}
		ll mid=(L+R)>>1;
		push_down(id,L,R);
		update_a(id<<1,L,mid,UL,UR,delta);
		update_a(id<<1|1,mid+1,R,UL,UR,delta);
		push_up(id);
		return;
	}
	void update_b(ll id,ll L,ll R,ll UL,ll UR,ll delta){
		if(L>R||UR<L||R<UL)return;
		if(UL<=L&&R<=UR){
			add_b(id,L,R,delta);
			return;
		}
		ll mid=(L+R)>>1;
		push_down(id,L,R);
		update_b(id<<1,L,mid,UL,UR,delta);
		update_b(id<<1|1,mid+1,R,UL,UR,delta);
		push_up(id);
		return;
	}
	ull query(ll id,ll L,ll R,ll QL,ll QR){
//		cout<<L<<" "<<R<<endl;
		if(L>R||QR<L||R<QL)return 0;
		if(QL<=L&&R<=QR)return ans[id];
		ll mid=(L+R)>>1;
		push_down(id,L,R);
		return query(id<<1,L,mid,QL,QR)+query(id<<1|1,mid+1,R,QL,QR);
	}
	ull debug(ll id,ll L,ll R,ll QL,ll QR){
//		cout<<L<<" "<<R<<endl;
		if(L>R||QR<L||R<QL)return 0;
		if(QL<=L&&R<=QR)return sum[id];
		ll mid=(L+R)>>1;
		push_down(id,L,R);
		return query(id<<1,L,mid,QL,QR)+query(id<<1|1,mid+1,R,QL,QR);
	}
}S;
ll res[MAXN];
int main(){
	cin>>T>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>t[i].l>>t[i].r;
		t[i].id=i; 
	}
	sort(t+1,t+1+q);
//	S.build(1,1,n);
	a[0]=b[0]=1e18;
	st_a[++top_a]=0;
	st_b[++top_b]=0;
	for(int i=1,j=1;i<=n;i++){
		S.update_a(1,1,n,i,i,a[i]);
		S.update_b(1,1,n,i,i,b[i]);
		ll pos=i;
		while(top_a&&a[st_a[top_a]]<a[i]){
			S.update_a(1,1,n,st_a[top_a],pos-1,a[i]-a[st_a[top_a]]);
//			cout<<st_a[top_a]<<" --- "<<pos-1<<" a"<<endl;
			pos=st_a[top_a];
			top_a--;
		}
		st_a[++top_a]=a[i];
		pos=i;
		while(top_b&&b[st_b[top_b]]<b[i]){
			S.update_b(1,1,n,st_b[top_b],pos-1,b[i]-b[st_b[top_b]]);
			pos=st_b[top_b];
			top_b--;
		}
		st_b[++top_b]=b[i];
		S.add_time(1,1,n,1);
		while(j<=q&&t[j].r==i){
			res[t[j].id]=S.query(1,1,n,t[j].l,t[j].r);
			j++;
		}
//		cout<<"debug "<<S.debug(1,1,n,1,i)<<'\n';
	}
	for(int i=1;i<=q;i++)cout<<res[i]<<'\n';
	return 0;
}