loj#P2495. 「AHOI / HNOI2018」转盘

「AHOI / HNOI2018」转盘

题目描述

一次小 G 和小 H 原本准备去聚餐,但由于太麻烦了于是题面简化如下:

一个转盘上有摆成一圈的 nn 个物品(编号 11nn)其中第 ii 个物品会在 TiT_i 时刻出现。

00 时刻时,小 G 可以任选 nn 个物品中的一个,我们将其编号记为 s0s_0。并且如果 ii 时刻选择了物品 sis_i,那么 i+1i + 1 时刻可以继续选择当前物品或者选择下一个物品。当 sis_inn 时,下一个物品为物品 11,否则下一个物品为 si+1s_{i} + 1。在每一时刻(包括 00 时刻),如果小 G 所选择的物品已经出现了,那么小 G 将会标记它。小 H 想知道,在物品选择的最优策略下,小 G 什么时候能标记所有物品?

但麻烦的是,物品的出现时间会不时修改。我们将其描述为 mm 次修改,每次修改将改变其中一个物品的出现时间。每次修改之后,你也需要求出当前局面的答案。对于其中部分测试点,小 H 还追加了强制在线的要求。

输入格式

第一行三个非负整数 n,m,pn,m,p,代表一共有 nn 个物品,mm 次修改。pp 只有 0011 两种取值,强制在线时 pp11,否则为 00。本节后面将解释如何使用 pp

接下来一行,有 nn 个用空格隔开的非负整数,第 ii 个数 TiT_i 代表物品 ii 的出现时间。

接下来 mm 行,每行两个非负整数 x,yx,y,代表一次修改及询问。修改方式如下:

  • 如果 p=0p = 0,则表示物品 xx 的出现时间 TxT_x 修改为 yy
  • 如果 p=1p = 1,则先将 xxyy 分别异或 LastAnsLastAns 得到 xx′yy′:即 x=xLastAns,y=yLastAnsx′ = x \oplus LastAns, y′ = y \oplus LastAns。然后将物品 xx′ 的出现时间 TxT_{x′} 修改为 yy′ 。其中的 LastAnsLastAns 是前一个询问的答案;特别的,第一次修改时的 LastAnsLastAns 为初始局面的答案。其中的 \oplus 为按位异或运算,例如 12=3,45=1,611=131 \oplus 2 = 3,4 \oplus 5 = 1,6 \oplus 11 = 13

保证输入合法。

输出格式

第一行一个整数代表初始局面的答案。

接下来 m+1m + 1 行每行一个整数分别代表每次修改后的答案。

5 3 0
1 2 3 4 5
3 5
5 0
1 4
5
7
6
7

数据范围与提示

测试点编号 nn mm Ti/TxT_i/T_x pp
1 10\le 10 =0=0
2 1000\le 1000 =0=0 1000\le 1000
3 105\le 10^5 105\le 10^5
4 5000\le 5000
5 8×104\le 8\times 10^4
6 =1=1
7 9×104\le 9\times 10^4 =0=0
8 =1=1
9 105\le 10^5 =0=0
10 =1=1