#P18523. Game of Votes
Game of Votes
Game of Votes
有 个人,编号为 。对于每个 ,第 个人讨厌一个人 ,其中 。第 个人不讨厌任何人。
一天,他们参加了一个共进行 轮的投票游戏。游戏开始时,没有人被淘汰。每一轮依次执行下列过程:
- 每个尚未被淘汰的人 先获得 票。
- 对于每个尚未被淘汰的人 ,如果他讨厌的人 也尚未被淘汰,那么他给 投 票。
- 在所有尚未被淘汰的人中,获得票数最多的人被淘汰。如果最多票数对应多个人,则淘汰其中编号最大的人。
各轮票数独立统计,上一轮的票数不会累积到下一轮。
在游戏开始之前发生了 个事件,事件分为两类:
- 给定 ,将 修改为 。
- 给定两个不同的人 ,询问:如果此刻用当前参数从头进行一场游戏, 中谁会先被淘汰?
请回答所有第二类事件。询问只要求计算结果,不会实际改变之后事件使用的参数,也不会保留任何淘汰状态。
输入格式
第一行包含两个正整数 (),分别表示人数和事件数。
第二行包含 个整数 ,满足 。当 时,这一行没有整数。
第三行包含 个整数 ,满足 。
第四行包含 个整数 ,满足 。
接下来 行,每行描述一个事件:
1 p x y:将 修改为 。保证 ,。2 c d:询问当前参数下, 中谁先被淘汰。保证 且 。
输入只有一组数据。
输出格式
对于每个第二类事件,输出一行一个字符。如果 先被淘汰,输出 0;否则输出 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