loj#P2495. 「AHOI / HNOI2018」转盘
「AHOI / HNOI2018」转盘
题目描述
一次小 G 和小 H 原本准备去聚餐,但由于太麻烦了于是题面简化如下:
一个转盘上有摆成一圈的 个物品(编号 至 )其中第 个物品会在 时刻出现。
在 时刻时,小 G 可以任选 个物品中的一个,我们将其编号记为 。并且如果 时刻选择了物品 ,那么 时刻可以继续选择当前物品或者选择下一个物品。当 为 时,下一个物品为物品 ,否则下一个物品为 。在每一时刻(包括 时刻),如果小 G 所选择的物品已经出现了,那么小 G 将会标记它。小 H 想知道,在物品选择的最优策略下,小 G 什么时候能标记所有物品?
但麻烦的是,物品的出现时间会不时修改。我们将其描述为 次修改,每次修改将改变其中一个物品的出现时间。每次修改之后,你也需要求出当前局面的答案。对于其中部分测试点,小 H 还追加了强制在线的要求。
输入格式
第一行三个非负整数 ,代表一共有 个物品, 次修改。 只有 或 两种取值,强制在线时 为 ,否则为 。本节后面将解释如何使用 。
接下来一行,有 个用空格隔开的非负整数,第 个数 代表物品 的出现时间。
接下来 行,每行两个非负整数 ,代表一次修改及询问。修改方式如下:
- 如果 ,则表示物品 的出现时间 修改为 。
- 如果 ,则先将 和 分别异或 得到 和 :即 。然后将物品 的出现时间 修改为 。其中的 是前一个询问的答案;特别的,第一次修改时的 为初始局面的答案。其中的 为按位异或运算,例如 。
保证输入合法。
输出格式
第一行一个整数代表初始局面的答案。
接下来 行每行一个整数分别代表每次修改后的答案。
5 3 0
1 2 3 4 5
3 5
5 0
1 4
5
7
6
7
数据范围与提示
测试点编号 | ||||
---|---|---|---|---|
1 | ||||
2 | ||||
3 | ||||
4 | ||||
5 | ||||
6 | ||||
7 | ||||
8 | ||||
9 | ||||
10 |