《自我宣传》

#include <cstdio>
#include <cstdlib>
#include <algorithm>

//using namespace std;

struct node
{
	int l,r,id;
}p[600000];

int n,m,one,len=0;
int a[600000],b[600000];
int s[600000],pos[600000];
int   q[600000]={},tail=0;
int ans[600000]={};
int aaa[600000]={};

inline int rd()
{
	int s=0;char x='x';
	while(x<'0'||x>'9')x=getchar();
	while(x>='0'&&x<='9'){s=s*10+(x^48);x=getchar();}
	return s;
}

inline int lowbit(int x){return x&(-x);}
inline void add(int x,int s){while(x<=n){aaa[x]+=s;x+=lowbit(x);}}
inline int getsum(int x){int res=0;while(x){res+=aaa[x];x-=lowbit(x);}return res;}
inline int summ(int l,int r){return getsum(r)-getsum(l-1);}

inline void print(int s)
{
	char ans[25],l=0;
	do
	{
		ans[++l]=s%10+'0';
		s/=10;
	}while(s>0);
	while(l)putchar(ans[l--]);
	putchar('\n');
}

inline bool bi1(node x,node y){return x.l>y.l;}
inline bool bi2(int x,int y){return s[x]>s[y];}

int main()
{
	//freopen("stack.in","r",stdin);
	//freopen("stack.out","w",stdout);
	
	n=rd();m=rd();
	for(int i=1;i<=n;i++)a[i]=rd(),pos[i]=i;
	for(int i=1;i<=n;i++)b[i]=rd();
	
	for(int i=1;i<=m;i++)
	{
		//cout<<i<<' '<<p[i].l<<' '<<p[i]
		p[i].l=rd();
		p[i].r=rd();
		p[i].id=i;
	}
	
	for(int i=1;i<=n;i++)
	{
		while(!(tail<=0||(a[i]!=a[q[tail]]&&b[i]<b[q[tail]])))tail--;
		s[i]=q[tail];
		q[++tail]=i;
		//cout<<s[i]<<' ';
		add(i,1);
	}
	
	std::sort(p+1,p+1+m,bi1);
	std::sort(pos+1,pos+1+n,bi2);
	
	for(int i=1,j=1;i<=m;i++)
	{
		while(j<=n&&s[pos[j]]>=p[i].l)
		{
			add(pos[j],-1);
			j++;
		}
		ans[p[i].id]=summ(p[i].l,p[i].r);
	}
	
	for(int i=1;i<=m;i++)print(ans[i]);
	
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}