题目描述

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

一个转盘上有摆成一圈的 

n

 个物品(编号1~ 

n

 ),其中的 

i

 个物品会在 

T_i

 时刻出现。

在0时刻时,小G可以任选 

n

 个物品中的一个,我们将其编号为 

s_0

 。并且如果 

i

 时刻选择了物品 

s_i

 ,那么 

i+1

时刻可以继续选择当前物品或选择下一个物品。当 

s_i

  

n

 时,下一个物品为物品 

1

 ,否则为物品 

s_{i}+1

 。在每一时刻(包括0时刻),如果小G选择的物品已经出现了,那么小G将会标记它。小H想知道,在物品选择的最优策略下,小G什么时候能标记所有物品?

但麻烦的是,物品的出现时间会不时修改。我们将其描述为 

m

 次修改,每次修改将改变其中一个物品的出现时间。每次修改后,你也需求出当前局面的答案。对于其中部分测试点,小H还追加了强制在线的要求。

输入输出格式

输入格式:

第一行三个非负整数 

n

  

m

  

p

 ,代表一共有 

n

 个物品, 

m

 次修改。 

p

 只有0或1两种取值,强制在线时 

p

 为1,否则 

p

 为0.

接下来一行,有 

n

 非负整数,第 

i

 个数 

T_i

 代表物品 

i

 的出现时间。

接下来 

m

 行,每行两个非负整数 

x

  

y

 ,代表一次修改及询问。修改方式如下:

(1)如果 

p=0

 ,则表示物品 

x

 的出现时间 

T_x

 修改为 

y

 

(2)如果 

p=1

 ,在先将 

x

  

y

 分别异或 

LastAns

 ,得到 

x’

  

y’

 ,然后将物品 

x’

 的出现时间 

T_{x’}

 修改为 

y’

 。其中的 

LastAns

 是前一个询问的结果;特别的,第一次修改时 

LastAns

 为初始局面的答案。

保证输入合法。

输出格式:

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

接下来 

m

 行每行一个整数,分别代表每次修改后的答案。

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

非常有趣的一题 很喜欢..

首先应该都能想到 一定不会经过某个点两次

那么考虑不妨我们让等待时间都在第一个点等待即可

这样一定不会差 因为考虑如果在中间一个点等待的话相当于他前面的点都提早到达并不会使得答案变得更优

那么相当于我们要求的是针对每个起点的出发的  (长度区间为n的这么一段区域所有的出现时间减去出发时间的最大值   ) 这么一个东西取min  最后再加上整个区间走完的代价即可

考虑线段树维护

那么设a[i]表示T[i]-i

考虑设mx[x]表示线段树上这个区间 a的最大值

ans[x]表示这个区间 左半边为起点 完全包含右区间所有a值中最大的最小值

即最后的ans[1]即是答案 考虑在线段树维护答案的时候 可能区间长度会大于我们需要的规定长度的n的那个区间 但是并不妨碍 因为超过时候我们发现超过区间的值其实是包含了 如 T[l],T[l+n]这样的东西 但是因为T[l+n]的值比T[l]的值小 那么可以知道这并不会对我们最后的答案产生影响

最后祭出 学习了哪个大佬的blog  orzz

https://blog.csdn.net/litble/article/details/80187830

 

分类: 线段树

elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论