记录编号	570428	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI Online 2022 1st]丹钓战	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	3.564 s
提交时间	2022-03-31 18:31:43	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;
	char a;
	a=getchar();
	while(a<'0'||a>'9') a=getchar();
	while(a>='0'&&a<='9') 
	{
		x=(x<<3)+(x<<1)+(a^48);
		a=getchar();
	}
	return x;
} 
int write(int x)
{
	if(x/10) write(x/10);
	putchar(x%10+48);
}
//////////////////////////////
const int MAXN=1e6+10;
int nc,qc;
int a[MAXN],b[MAXN];
int st[21][MAXN][2];//ST表(每个区间里的最小值的峰高及位置)
void BJ()
{
	int z[MAXN][2]={0};
	int cl=0;
	for(int i=1;i<=nc;i++)
	{
		while(z[cl][0]==a[i]&&cl!=0||z[cl][1]<=b[i]&&cl!=0) cl--;
		z[++cl][0]=a[i];
		z[cl][1]=b[i];
		st[0][i][0]=cl;
		st[0][i][1]=i; 
	}
	return;
}
void BUILD()
{
	for(int i=1,i2=1;i<=20;i++)
	{
		i2<<=1;
		for(int o=1;o+i2-1<=nc;o++)
		{
			if(st[i-1][o][0]<st[i-1][o+(i2>>1)][0])
			{
				st[i][o][0]=st[i-1][o][0];
				st[i][o][1]=st[i-1][o][1];
			} 
			else
			{
				st[i][o][0]=st[i-1][o+(i2>>1)][0];
				st[i][o][1]=st[i-1][o+(i2>>1)][1];
			}
		} 
	}
}
struct QXX
{
	int ar;
	int nx;
}g[MAXN<<1];
int gj;
int hd[MAXN];
int dep[MAXN];
inline void ADD(int x,int y)
{
	g[++gj].ar=y;
	g[gj].nx=hd[x];
	hd[x]=gj; 
	return;
}
void TREB()
{
	deque<int> t[2];//峰高和位置 
	for(int i=1;i<=nc;i++)
	{
		while(t[0].size()&&st[0][i][0]<=t[0].back())
		{
			ADD(i,t[1].back());
			t[0].pop_back();
			t[1].pop_back();
		}
		t[0].push_back(st[0][i][0]);
		t[1].push_back(i);
	}
	return;
}
void DFS(int cl,int de)
{
	dep[cl]=de;
	for(int i=hd[cl];i;i=g[i].nx) DFS(g[i].ar,de+1);
	return;
}
inline int MID(int x,int y)
{
	int re=0;
	int sum=y-x;
	while((1<<re)<=sum) re++;
	return re-1;
}
int main()
{
	freopen("noi_online2022_stack.in","r",stdin);
	freopen("noi_online2022_stack.out","w",stdout);
	nc=read();
	qc=read();
	for(int i=1;i<=nc;i++) a[i]=read();
	for(int i=1;i<=nc;i++) b[i]=read();
	BJ();//标记 
//	memset(st,0x3f,sizeof(st));
	BUILD();//建ST表
//	cout<<"P1\n";
	TREB();//树剖 
//	cout<<"P2\n";
	for(int i=nc;i;i--)
		if(!dep[i]){DFS(i,1);}//统计长度 
	int s1,s2,s3,ans;
//	cout<<"序号&&长度：\n";
//	for(int i=1;i<=nc;i++) cout<<i<<": "<<st[0][i][0]<<" "<<dep[i]<<endl;
//	cout<<"OV1\n";
	for(int i=1,sum;i<=qc;i++)
	{
		s1=read();
		s2=read();
		if(s1==s2)
		{
			printf("1");
			putchar(10);
			continue;
		}
// 		cout<<"CSS:"<<i<<":"<<s1<<" "<<s2<<endl;
		s3=MID(s1,s2);
		if(st[s3][s1][0]<st[s3][s2-(1<<s3)+1][0])
		{sum=st[s3][s1][1];}
		else
		{sum=st[s3][s2-(1<<s3)+1][1];}
		ans=dep[s1]-dep[sum]+1;
//		cout<<"CS:"<<sum<<" "<<s3<<" "<<st[s3][s1][0]<<" "<<st[s3][s2-(1<<s3)+1][0]<<"; "<<dep[s1]<<" "<<dep[sum]<<endl;
		write(ans);
		putchar(10);
	}
	return 0;
} 
//my 0
//ans 1