记录编号	593119	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2022]比赛	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	14.168 s
提交时间	2024-08-21 18:58:25	内存使用	41.11 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 3e5+10,M = N<<2;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int T,n,q;
struct tag{
	ull lc,ld,t,hc,hd,s;
	tag operator + (const tag x)const{
		if(t == -1)return x;
		return{lc + x.lc,ld + x.ld,t + x.t,
		hc + x.hc + lc * x.t,hd + x.hd + ld * x.t,
		s + x.s + lc * ld * x.t + lc * x.hd + ld * x.hc};
	}
};
struct dat{
	ull len,sc,sd,cd,scd;
	dat operator + (const dat x)const{
		return{len + x.len,sc + x.sc,sd + x.sd,cd + x.cd,scd + x.scd};
	}
	dat operator + (const tag x)const{
		return {len,sc + x.lc * len,sd + x.ld * len,
		cd + sc * x.ld + sd * x.lc + len * x.lc * x.ld,
		scd + x.t * cd + sc * x.hd + sd * x.hc + len * x.s};
	}
};
struct segment{
	tag la[M];dat s[M]; 
	void pushup(int p){s[p] = s[p<<1] + s[p<<1|1];};
	void update(int p,tag k){s[p] = s[p] + k,la[p] = la[p] + k;}
	void pushdown(int p){
		if(la[p].t == -1)return;
		update(p<<1,la[p]),update(p<<1|1,la[p]);
		la[p].t = -1;
	}
	void build(int p,int l,int r){
		s[p].len = r - l + 1,la[p].t = -1;
		if(l == r)return;
		int mid = l + r >> 1;
		build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	}
	void modify(int p,int l,int r,int L,int R,tag k){
		if(L <= l && r <= R)return update(p,k),void();
		int mid = l + r >> 1;
		pushdown(p);
		if(L <= mid)modify(p<<1,l,mid,L,R,k);
		if(R > mid)modify(p<<1|1,mid+1,r,L,R,k);
		pushup(p);
	}
	ull ask(int p,int l,int r,int L,int R){
		if(r < L || l > R)return 0;
		if(L <= l && r <= R)return s[p].scd;
		int mid = l + r >> 1;
		pushdown(p);
		return ask(p<<1,l,mid,L,R) + ask(p<<1|1,mid+1,r,L,R);
	}
}t;


ull a[N],b[N];
vector<pii>G[N];
int st1[N],st2[N],top1,top2; 
ull ans[N];
int main(){
	freopen("noip2022_match.in","r",stdin);
	freopen("noip2022_match.out","w",stdout);
	T = read(),n = read();
	for(int i = 1;i <= n;i++)a[i] = read();
	for(int i = 1;i <= n;i++)b[i] = read();
	q = read();
	for(int i = 1;i <= q;i++){
		int l = read(),r = read();
		G[r].pb(mp(l,i));
	}
	t.build(1,1,n);
	a[0] = b[0] = n + 1;
	for(int i = 1;i <= n;i++){
		while(top1 && a[st1[top1]] < a[i]){
			t.modify(1,1,n,st1[top1 - 1] + 1,st1[top1],{-a[st1[top1]],0,0});
			top1--;
		}
		t.modify(1,1,n,st1[top1] + 1,i,{a[i],0,0});
		st1[++top1] = i;
		while(top2 && b[st2[top2]] < b[i]){
			t.modify(1,1,n,st2[top2 - 1] + 1,st2[top2],{0,-b[st2[top2]],0});
			top2--;
		}
		t.modify(1,1,n,st2[top2] + 1,i,{0,b[i],0});
		st2[++top2] = i;
		t.modify(1,1,n,1,i,{0,0,1,0,0,0});
		for(pii now : G[i])ans[now.se] = t.ask(1,1,n,now.fi,i);
	}
	for(int i = 1;i <= q;i++)cout<<ans[i]<<endl;

	return 0;

}