rt.写了一个莫队+平衡树，时间复杂度 $O(n\sqrt{n}log(n))$,TLE$*$13,AC$*$10

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct query{
	int l,r,id;
}q[10005];
int a[100005],b[100005],k,n,p[100005],len,res,ans[10005],s[100005];
bool cmp(query a,query b){return p[a.l]!=p[b.l]?p[a.l]<p[b.l]:a.r<b.r;}
struct fhq{
	struct treap{
		int l,r,val,pri,sz,sum;
	}t[400005];
	int root,x,y,z;
	stack<int>trash;
	void init(){
		for(int i=400000;i>=1;i--) trash.push(i);
	}
	void update(int x){
		t[x].sz=t[t[x].l].sz+t[t[x].r].sz+1;
		t[x].sum=t[t[x].l].sum+t[t[x].r].sum+t[x].val;
	}
	void split(int u,int v,int&x,int&y){
		if(!u) x=y=0;
		else{
			if(t[u].val<=v){
				x=u;
				split(t[u].r,v,t[u].r,y);
			}else{
				y=u;
				split(t[u].l,v,x,t[u].l);
			}
			update(u);
		}
	}
	int merge(int x,int y){
		if(x==0||y==0) return x+y;
		if(t[x].pri<t[y].pri){
			t[x].r=merge(t[x].r,y);
			update(x);
			return x;
		}else{
			t[y].l=merge(x,t[y].l);
			update(y);
			return y;
		}
	} 
	int create(int v){
		int id=trash.top();
		trash.pop();
		t[id]=treap{0,0,v,rand(),1,v};
		return id;
	}
	void insert(int a){
		split(root,a,x,y);
		root=merge(merge(x,create(a)),y);
	}
	void erase(int a){
		split(root,a,x,z);
		split(x,a-1,x,y);
		trash.push(y);
		y=merge(t[y].l,t[y].r);
		root=merge(merge(x,y),z);
	}
}ta,tb;
void adda(int x){
	int l,r;
	tb.split(tb.root,a[x],l,r);
	res+=tb.t[l].sz*a[x]-tb.t[l].sum;
	res+=tb.t[r].sum-tb.t[r].sz*a[x];
	tb.root=tb.merge(l,r);
	ta.insert(a[x]);
}
void dela(int x){
	int l,r;
	ta.erase(a[x]);
	tb.split(tb.root,a[x],l,r);
	res-=tb.t[l].sz*a[x]-tb.t[l].sum;
	res-=tb.t[r].sum-tb.t[r].sz*a[x];
	tb.root=tb.merge(l,r);
}
void addb(int x){
	int l,r;
	ta.split(ta.root,b[x],l,r);
	res+=ta.t[l].sz*b[x]-ta.t[l].sum;
	res+=ta.t[r].sum-ta.t[r].sz*b[x];
	ta.root=ta.merge(l,r);
	tb.insert(b[x]);
}
void delb(int x){
	int l,r;
	tb.erase(b[x]);
	ta.split(ta.root,b[x],l,r);
	res-=ta.t[l].sz*b[x]-ta.t[l].sum;
	res-=ta.t[r].sum-ta.t[r].sz*b[x];
	ta.root=ta.merge(l,r);
}
signed main(){
	ta.init();
	tb.init();
	cin>>n;
	len=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) p[i]=(i-1)/len+1;
	cin>>k;
	for(int i=1;i<=k;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+k+1,cmp);
	int l=0,r=0;
	for(int i=1;i<=k;i++){
		while(q[i].l>l) adda(++l);
		while(q[i].r>r) addb(++r);
		while(q[i].l<l) dela(l--);
		while(q[i].r<r) delb(r--);
		ans[q[i].id]=res;
	}
	for(int i=1;i<=k;i++) cout<<ans[i]<<endl;
	return 0;
}