QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+13]
Statistics

n 个人,由 1n 编号。第 i(2in) 个人有一个讨厌的人 fi(1fi<i),第 1 个人没有讨厌的人。

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

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

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

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

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

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

输入格式

从标准输入读入数据。

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

第二行 (n1) 个整数 f2,f3,,fn

第三行 n 个整数 a1,a2,,an

第四行 n 个整数 b1,b2,,bn

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

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

输出格式

输出到标准输出。

对于每个 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

子任务

对于所有测试数据,

  • 1n,q2×105
  • 2in,1fi<i
  • 0ai,bi,x,y108
  • 1c,d,pn
  • cd
子任务编号子任务分值nq特殊性质
15500500
21030003000
32×1052×105fi[1,i1] 中均匀随机
415fi=1
530fi=i1
6