问题1160--卡牌之谜

1160: 卡牌之谜

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 256 MB

题目描述

天才程序员菜哭武对于卡牌游戏有着深深的热爱。这一天,菜哭武的家中闯入了一个神秘黑衣男子,这个神秘黑衣男子要和菜哭武玩一个游戏,奖励是一张五百万元的支票。
这个游戏规则是这样的:黑衣男子手上有n张牌,在地上排成一个序列,这些牌有的正面朝上,有的背面朝上。所有牌的背面都是空白的,而每张牌的正面都写有一个数字,具体而言,第i张牌(即从左往右数位置为i的卡牌)的正面写有一个数字pi。p1, p2, p3....pn这n个数字刚好构成了1~n的一个排列。
这个游戏会进行q个回合,每个回合,黑衣男子要么会将一张牌翻面,要么会问菜哭武一个问题。这个问题是这样的:如果菜哭武每次只能将正面朝上的牌翻面,那么菜哭武最少要变多少次魔术才能将所有正面朝上的牌翻成都是背面。众所周知,由于菜哭武是一个技艺高超的魔术师,他每变一次魔术,都会将一张正面朝上的牌翻面,之后如果这张牌正面上写的数字是x且第x张牌此时也是正面朝上的,第x张牌也会被翻到背面,然后是第px张牌....以此类推, 直到对应位置的牌为背面结束。
当然黑衣人只想知道最小的次数,因此菜哭武只能在心里估计所需要的次数,而不会真的去变魔术。菜哭武想要拿到这笔钱买显卡,所以他需要对于每个询问给出正确的答案。

输入

第一行两个正整数n和q(1 <= n, q <= 105), 代表卡牌的总数和黑衣人询问的个数。
第二行n个正整数pi(1 <= i <= n, 1 <= pi <= 105 且p1~pn是1~n的一个排列)。
第三行n个正整数si(1 <= i <= n, si = 0或1),若si = 0代表第i张牌正面朝上,若si = 1代表第i张牌背面朝上。
之后q行,每行开头一个数字op, 代表黑衣人执行的操作类型,op = 1代表翻面,op = 2代表询问。
若op = 1,接下来会有一个数字x,代表黑衣人将第x张牌翻面。
若op = 2, 则代表黑衣人询问菜哭武最少的变魔术次数。

输出

对于每一个op = 2的询问,输出一行整数,代表询问的结果。

样例输入 Copy

5 9
3 2 5 1 4
0 0 0 0 0 
2
1 2
2
1 1
2
1 5
2
1 2
2

样例输出 Copy

2
1
1
2
3

来源/分类