超级大常数线段树代码求卡常

#include<bits/stdc++.h>
#define mid ((le+ri)>>1)
#define ls (u<<1)
#define rs ((u<<1)|1)
#define lp ls,le,mid
#define rp rs,mid+1,ri
using namespace std;
typedef unsigned long long ll;
struct ms{
	ll sx,sy,sxy,s;
	ll len;
};
void pr_ms(ms &u){
	printf("%llu %llu %llu %llu %llu\n",u.sx,u.sy,u.sxy,u.s,u.len);
}
ms operator+(const ms &a,const ms &b){
	ms res=a;
	res.sx+=b.sx;
	res.sy+=b.sy;
	res.sxy+=b.sxy;
	res.s+=b.s;
	res.len+=b.len;
	return res;
}
struct tg{
	ll ax,ay,axy,ac,tx,ty;// first add,then set
	// s' = s + ac*len + ax*sx + ay*sy + axy*sxy
};
void pr_tg(tg &u){
	printf("%llu %llu %llu %llu %llu %llu\n",u.ax,u.ay,u.axy,u.ac,u.tx,u.ty);
}
tg operator*(const tg &a,const tg &b){// first use a then use b
	tg res=a;
	if(a.tx&&a.ty){
		res.ac+=a.tx*b.ax;
		res.ac+=a.ty*b.ay;
		res.ac+=a.tx*a.ty*b.axy;
		res.ac+=b.ac;
		if(b.tx) res.tx=b.tx;
		if(b.ty) res.ty=b.ty;
		return res;
	}
	if(a.tx){
		res.ac+=a.tx*b.ax;
		res.ay+=b.ay;
		res.ay+=a.tx*b.axy;
		res.ac+=b.ac;
		if(b.tx) res.tx=b.tx;
		if(b.ty) res.ty=b.ty;
		return res;
	}
	if(a.ty){
		res.ax+=b.ax;
		res.ac+=a.ty*b.ay;
		res.ax+=a.ty*b.axy;
		res.ac+=b.ac;
		if(b.tx) res.tx=b.tx;
		if(b.ty) res.ty=b.ty;
		return res;
	}
	res.ax+=b.ax;
	res.ay+=b.ay;
	res.axy+=b.axy;
	res.ac+=b.ac;
	if(b.tx) res.tx=b.tx;
	if(b.ty) res.ty=b.ty;
	return res;
}
void app(ms &a,tg &b){
	a.s+=b.ac*a.len+b.ax*a.sx+b.ay*a.sy+b.axy*a.sxy;
	if(b.tx&&b.ty){
		a.sx=b.tx*a.len;
		a.sy=b.ty*a.len;
		a.sxy=b.tx*b.ty*a.len;
	}
	else if(b.tx){
		a.sx=b.tx*a.len;
		a.sxy=b.tx*a.sy;
	}
	else if(b.ty){
		a.sy=b.ty*a.len;
		a.sxy=b.ty*a.sx;
	}
}
struct sgt{
	ms s[1000010];
	tg t[1000010];
	void det(){
		printf("--------------------\n");
		for(int i=1;i<=9;i++){
			printf("%d\n",i);
			pr_ms(s[i]);
			pr_tg(t[i]);
		}
	}
	void ch(int u,int le,int ri,tg &k){
		t[u]=t[u]*k;
		app(s[u],k);
	}
	void push_up(int u){
		s[u]=s[ls]+s[rs];
	}
	void push_down(int u,int le,int ri){
		ch(lp,t[u]);
		ch(rp,t[u]);
		t[u]=tg();
	}
	void build(int u,int le,int ri){
		if(le==ri){
			s[u].len=1;
			return;
		}
		build(lp);
		build(rp);
		push_up(u);
	}
	void upd(int u,int le,int ri,int x,int y,tg &k){
		if(x<=le&&ri<=y){
			ch(u,le,ri,k);
			return;
		}
		push_down(u,le,ri);
		if(x<=mid) upd(lp,x,y,k);
		if(y>mid) upd(rp,x,y,k);
		push_up(u);
	}
	ll que(int u,int le,int ri,int x,int y){
		if(x<=le&&ri<=y){
			return s[u].s;
		}
		push_down(u,le,ri);
		ll res=0;
		if(x<=mid) res+=que(lp,x,y);
		if(y>mid) res+=que(rp,x,y);
		return res;
	}
}t;
void tes(){
	t.build(1,1,5);
	
	tg t1={0,0,0,0,1,0};
	tg t2={0,0,0,0,0,1};
	tg t3={0,0,1,0,0,0};
	
	t.upd(1,1,5,2,4,t1);
	
	t.upd(1,1,5,3,5,t2);
	
	t.upd(1,1,5,1,3,t3);
	
	tg ts={0,0,0,0,2,0};
	t.upd(1,1,5,1,2,ts);
	
	ts={0,0,0,0,0,4};
	t.upd(1,1,5,2,4,ts);
	
	ts={0,0,1,0,0,0};
	t.upd(1,1,5,1,4,t3);
	
	for(int i=1;i<=5;i++){
		printf("%llu ",t.que(1,1,5,i,i));
	}
//	t.det();
//	printf("%llu ",t.que(1,1,1,1,1));
}
vector<pair<int,int> > q[250010];
int n,m,a[250010],b[250010];
int pa[250010],sa[250010],ta,pb[250010],sb[250010],tb;
ll ans[250010];
int main(){
	scanf("%d%d",&n,&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		q[y].push_back({x,i});
	}
	t.build(1,1,n);
	for(int i=1;i<=n;i++){
		// a
		while(ta&&sa[ta]<a[i]) ta--;
		int u=pa[ta]+1;
		tg opt={0,0,0,0,(ll)a[i],0};
		t.upd(1,1,n,u,i,opt);
		sa[++ta]=a[i];
		pa[ta]=i;
		// b
		while(tb&&sb[tb]<b[i]) tb--;
		int v=pb[tb]+1;
		opt={0,0,0,0,0,(ll)b[i]};
		t.upd(1,1,n,v,i,opt);
		sb[++tb]=b[i];
		pb[tb]=i;
		// cal
		opt={0,0,1,0,0,0};
		t.upd(1,1,n,1,i,opt);
		for(int j=0;j<(int)q[i].size();j++){
			int w=q[i][j].first,id=q[i][j].second;
			ans[id]=t.que(1,1,n,w,i);
		}
	}
	for(int i=1;i<=m;i++){
		printf("%llu\n",ans[i]);
	}
}