QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[-9]

# 8749. 贸易

Statistics

题目背景

小 Z 生活的学校就像是一条链,直径很长,宽度很窄。

具体来说,这里有一个长度为 n 的序列,每个位置有一个属性 ai{0/1} 和一个类型 ci,在这里有一些贸易事件会发生。

小 Z 从左往右通过这个序列,若当前遇到一个 0 属性的节点,则小 Z 可以购入至多一个 ci 类型的物品,若当前遇到一个 1 属性的节点,则小 Z 可以卖出至多一个 ci 类型的物品,显然,在小 Z 没有这种类型的物品时是不能卖出的。

一次合法的交易定义为从某个节点买入,并在某个节点卖出,注意,你需要保证在最后小 Z 手里不存在任何东西。

给出 q 次询问,每次小 Z 从 li 顺序走到 ri,问:最大合法交易次数是多少

q 次询问,每次给定一个区间,顺序枚举区间元素,遇到属性为 0 就购入一个该颜色的物品,遇到 1 就卖出这个颜色的物品,权值定义为成功卖出的次数(当前购入 - 卖出 1 时可以成功卖出)。

输入格式

从标准输入读入数据。

第一行两个正整数 n,q

接下来一行 n 个数,第 i 个表示 ai

接下来一行 n 个数,第 i 个表示 ci

接下来 q 行,每行两个数表示 li,ri

输出格式

输出到标准输出。

输出共 q 行,每行一个数表示当前这个询问中的最大合法交易次数。

样例

输入

10 5
1 1 0 0 0 0 0 1 1 1 
1 1 1 1 1 1 1 1 1 1 
4 6
2 4
2 6
7 10
4 7

输出

0
0
0
1
0

解释

子任务

对于所有数据,满足 1n,q5×105,1cin,1lirin,ai{0,1}

提示

请注意输入输出效率。