记录编号	570490	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI Online 2022 1st]丹钓战	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	5.332 s
提交时间	2022-04-06 20:19:33	内存使用	0.00 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500005;
int n,m,a[maxn],b[maxn],stk[maxn],top,L[maxn];
struct query {
	int x,y,id;
	query() {
		x = y = id = 0;
	}
	bool operator < (const query& p)const {
		return y < p.y;
	}
}Q[maxn];
int c[maxn];
int lowbit(int x) {
	return x & -x;
}
void add(int x,int y) {
	if(!x)return ;
	for(;x <= n;x += lowbit(x))c[x] += y;
	return ;
}
int query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))ans += c[x];
	return ans;
}
int ans[maxn];
int main() {
	freopen("noi_online2022_stack.in","r",stdin);
	freopen("noi_online2022_stack.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
	for(int i = 1;i <= n;++ i)scanf("%d",&b[i]);
	for(int i = 1;i <= n;++ i) {
		while(top&&(a[stk[top]] == a[i]||b[stk[top]] <= b[i]))stk[top --] = 0;
		L[i] = stk[top];
		stk[++ top] = i;
	}
	for(int i = 1;i <= m;++ i) {
		Q[i].id = i;
		scanf("%d%d",&Q[i].x,&Q[i].y);
	}
	sort(Q + 1 , Q + 1 + m);
	for(int i = 1,j = 1;i <= m;++ i) {
		for(;j <= Q[i].y;++ j) {
			if(!L[j])continue ;
			add(L[j] , 1);
		}
		ans[Q[i].id] = Q[i].y - Q[i].x + 1 - query(Q[i].y) + query(Q[i].x - 1); 
	}
	for(int i = 1;i <= m;++ i)printf("%d\n",ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}