$O(q\log^2n)$ 被卡了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,q,a[maxn],b[maxn],c[maxn];
inline int read(){
	int res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^'0');
		ch=getchar();
	}
	return res;
}
stack<int> stk;
struct Treap{
	struct T{
		int w,sz,num,fix,son[2];
	};
	int tot;
	T tree[maxn*20];
	int newnode(int w){
		++tot;
		tree[tot].w=w;
		tree[tot].fix=rand();
		tree[tot].num=1;
		tree[tot].son[0]=tree[tot].son[1]=0;
		tree[tot].sz=1;
		return tot;
	}
	void pushup(int k){
		tree[k].sz=tree[tree[k].son[0]].sz+tree[tree[k].son[1]].sz+tree[k].num;
	}
	void rotate(int &k,int d){
		int y=tree[k].son[d];
		tree[k].son[d]=tree[y].son[d ^ 1];
		tree[y].son[d^1]=k;
		pushup(k);
		pushup(y);
		k=y;
	}
	void insert(int &k, int w){
		if(!k)
			k=newnode(w);
		else if(tree[k].w==w)
			++tree[k].num;
		else{
			if(tree[k].w>w){
				insert(tree[k].son[0],w);
				if(tree[tree[k].son[0]].fix>tree[k].fix)
					rotate(k,0);
			} else{
				insert(tree[k].son[1],w);
				if(tree[tree[k].son[1]].fix>tree[k].fix)
					rotate(k,1);
			}
		}
		pushup(k);
	}
	int rank(int k,int val){
		if(!k)
			return 0;
		if(tree[k].w>val)
			return rank(tree[k].son[0],val);
		else if(tree[k].w==val)
			return tree[tree[k].son[0]].sz;
		else
			return tree[tree[k].son[0]].sz+tree[k].num+rank(tree[k].son[1],val);
	}
}x;
struct Tree{
	struct T{
		int l,r,root;
	};
	T tree[maxn<<3];
	void Build(int k,int l,int r){
		tree[k].l=l;
		tree[k].r=r;
		for(int i=l;i<=r;++i)
			x.insert(tree[k].root,c[i]);
		if(l!=r){
			int mid=l+r>>1;
			Build(k<<1,l,mid);
			Build(k<<1|1,mid+1,r);
		}
	}
	int Rank(int k,int l,int r,int val){
		if(tree[k].l>r||tree[k].r<l)
			return 0;
		if(tree[k].l>=l&&tree[k].r<=r)
			return x.rank(tree[k].root,val);
		else
			return Rank(k<<1,l,r,val)+Rank(k<<1|1,l,r,val);
	}
}y;
int main(){
	n=read(),q=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		b[i]=read(),c[i]=-1;
	for(int i=1;i<=n;++i){
		while(!stk.empty()){
			if(a[i]!=a[stk.top()]&&b[i]<b[stk.top()]){
				c[i]=stk.top();
				break;
			}
			stk.pop();
		}
		stk.push(i);
	}
	y.Build(1,1,n);
	for(int i=1;i<=q;++i){
		int l=read(),r=read();
		printf("%d\n",y.Rank(1,l,r,l));
	}
	return 0;
}