UOJ Logo Universal Online Judge

UOJ

#806. 【UR #25】见贤思齐

附件下载 统计

跳蚤国有浓厚的工程师文化,其核心特征之一就是每个工程师都在“见贤思齐”。

跳蚤国一共有 $n$ 名工程师,其中第 $i$ 号工程师的技术水平可以用一个整数 $a_i$ 表示。

每名工程师还有一个在心中默默比较的对象,其中第 $i$ 号工程师的比较对象的编号可以记作 $p_i$。

在为伏特多轮(Polycycle)项目工作的过程中,这些工程师每天都会“见贤思齐”。即,每一天开始的时候,如果第 $p_i$ 号工程师的技术水平 $a_{p_i}$ 不小于第 $i$ 号工程师的技术水平 $a_i$,那么第 $i$ 号工程师就会加倍努力工作,使得他这一天结束的时候技术水平从 $a_i$ 增长到 $a_i + 1$。

跳蚤国王历来对项目进展十分重视。在这个工程师们互相切磋的过程中,他会进行 $q$ 次的质询。每次质询,他会给出一个工程师的编号 $g$ 和一个天数 $d$,你的任务就是帮助跳蚤国王预测在第 $d$ 天结束的时候编号为 $g$ 的工程师的技术水平。

输入格式

第一行:两个整数 $n,q$,表示工程师总数和质询总数。

第二行:$n$ 个整数 $a_1,\ldots,a_n$,表示每名工程师的技术水平。

第三行:$n$ 个整数 $p_1,\ldots,p_n$,表示每名工程师心中的比较对象编号。

接下来 $q$ 行:每行两个整数 $g,d$,表示一次质询。

输出格式

输出 $q$ 行:每行一个整数表示一个问题的答案。

样例一

input

4 12
4 9 5 8
2 3 4 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
4 1
4 2
4 3

output

5
6
7
9
9
9
6
7
8
9
10
10

样例二

见附件下载。该样例满足子任务 1 的限制。

样例三

见附件下载。该样例满足子任务 2 的限制。

样例四

见附件下载。该样例满足子任务 3 的限制。

样例五

见附件下载。该样例满足子任务 4 的限制。

样例六

见附件下载。该样例满足子任务 5 的限制。

数据范围

对于全部数据:$1\leq n,q\leq 2\times 10^5,\ 1\leq a_i\leq 10^9,\ 1\leq g,p_i\leq n,\ 1\leq d\leq 2\times 10^5$。

子任务编号 $n\leq$ $q\leq$ 特殊性质 分值
$1$ $1000$ $2\times 10^5$ $d\leq 1000$ $20$
$2$ $1000$ $20$
$3$ $2\times 10^5$ $2\times 10^5$ $p_i=\min(i+1,n)$ $20$
$4$ $70000$ $70000$ $20$
$5$ $2\times 10^5$ $2\times 10^5$ $20$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$