题目背景
小 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
解释
子任务
对于所有数据,满足 1≤n,q≤5×105,1≤ci≤n,1≤li≤ri≤n,ai∈{0,1}。
提示
请注意输入输出效率。