#2097. 投票游戏

    ID: 2097 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest1513来源:qoj.ac数据:公开样例模拟排序

投票游戏

投票游戏

题目描述

标题: 投票游戏 - Problem - QOJ.ac

#8222. 投票游戏

Statistics

The problem was used in the following contests:

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

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

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

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

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

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

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

输入格式

从标准输入读入数据。

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

第二行 (n−1) 个整数 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,你需要判断如果此时进行了一次游戏,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≤n,q≤2×105,
  • ∀2≤i≤n,1≤fi<i,
  • 0≤ai,bi,x,y≤108,
  • 1≤c,d,p≤n,
  • c≠d。

子任务编号子任务分值n≤q≤特殊性质15500500无2103000300032×1052×105fi 在 [1,i−1] 中均匀随机415fi=1530fi=i−16无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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
0
0
1
1
1
1