QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 8222. 投票游戏

Statistics

有 $n$ 个人,由 $1$ 至 $n$ 编号。第 $i (2 \le i \le n)$ 个人有一个讨厌的人 $f_i (1 \leq f_i < i)$,第 $1$ 个人没有讨厌的人。

这一天,$n$ 个人进行了一场关于投票的游戏。一次游戏会进行 $n$ 轮。游戏开始时,所有人都没有被票出。游戏的每一轮中,会进行以下过程:

  1. 对于每一个没有被票出的人 $i$,TA 初始有 $a_i$ 票。
  2. 随后,对于每一个没有被票出的人 $i$,如果 TA 有讨厌的人且 TA 讨厌的人 $f_i$ 没有被票出,则 TA 会给 $f_i$ 投 $b_i$ 票。
  3. 最后,票出当前没有被票出的人的票数最高的,如果有多个票数最高的人,票出其中编号最大的人。

一次游戏的 $n$ 轮之间独立计票。

在游戏开始前,发生了 $q$ 次事件,事件有以下两种:

  1. 给定 $p, x, y$,将 $(a_p, b_p)$ 修改为 $(x,y)$;
  2. 小明想知道,给定两个人 $c,d$,如果此刻进行一次游戏,两个人中谁先被票出。

作为小明的朋友,你可以帮帮小明吗?

输入格式

从标准输入读入数据。

第一行两个正整数 $n, q$,表示人数与发生的事件数。

第二行 $(n-1)$ 个整数 $f_2, f_3, \cdots, f_n$。

第三行 $n$ 个整数 $a_1, a_2, \cdots, a_n$。

第四行 $n$ 个整数 $b_1, b_2, \cdots, b_n$。

接下来 $q$ 行,每行三个或四个整数描述一个事件。第一个正整数 $op$ 表示发生事件的类型。

  • 若 $op=1$,则接下来三个整数 $p, x, y$,表示将 $(a_p, b_p)$ 修改为 $(x, y)$。
  • 若 $op=2$,则接下来两个正整数 $c, d$,你需要判断如果此时进行了一次游戏,$c$ 和 $d$ 谁先被票出。

输出格式

输出到标准输出。

对于每个 $op=2$ 的事件输出一行一个 01 字符,若 $c$ 先被票出输出 0,否则输出 1

样例1输入

5 8
1 2 3 2
1 3 2 1 0
0 4 1 0 0
2 1 3
1 1 0 3
2 2 5
1 1 2 2
2 4 3
2 5 4
2 5 1
2 2 1

样例1输出

0
0
1
1
1
1

子任务

对于所有测试数据,

  • $1 \le n, q \le 2 \times 10^5$,
  • $\forall 2 \le i \le n, 1 \le f_i < i$,
  • $0 \le a_i, b_i, x, y \le 10^8$,
  • $1 \le c, d, p \le n$,
  • $c \ne d$。
子任务编号子任务分值$n \leq$$q \leq$特殊性质
15$500$$500$
210$3000$$3000$
3$2\times 10^5$$2 \times 10^5$$f_i$ 在 $[1, i - 1]$ 中均匀随机
415$f_i = 1$
530$f_i = i-1$
6