- 有\(n\)个物品摆成一个环，第\(i\)个物品会在第\(T_i\)个时刻出现。
- 初始你可以选中一个物品，每个时刻你可以继续选择当前物品，或是选择后一个物品。如果你当前选中的物品出现了，这个物品就会被标记。
- 问最少需要多久才能标记所有物品。
- \(q\)次修改，每次单点修改\(T_i\)，你需要给出初始局面以及每次修改之后的答案。
- \(n,q\le10^5\)，强制在线
从最后位置开始的倒推
环的问题显然比较诡异，所以我们考虑把数组复制一遍，这样就可以破环为链。
根据选中的初始位置开始的最优策略比较复杂，因此我们不妨考虑最后的位置\(i\)，那么问题就变成了向前走，而物品\(j\)会在第\(T_{j}-1\)个时刻消失。
发现这时我们就不可能停在某一个位置，一直向前走必然是最优的。
于是，对于最终位置\(i\)的答案就应该是：
\[\max_{j=i-n+1}^i(T_j+i-j) \]其中的\(i\)显然可以提出，得到：
\[i+\max_{j=i-n+1}^i(T_j-j) \]由于当\(j>i\)之后，\(T_j=T_{j-n},j>j-n\)，所以\(T_j-j\)必然小于\(T_{j-n}-(j-n)\)，即便计入贡献也没有关系，因此方便起见我们可以直接把所有\(j\)的上界都调成\(2n-1\)。
于是得到总的答案就是：
\[\min_{i=n}^{2n-1}(i+\max_{j=i-n+1}^{2n-1}(T_j-j)) \]发现\(j\)的下标从\(i-n+1\)开始似乎不太好看，索性把\(i\)直接减去\(n-1\)，得到：
\[\min_{i=1}^n(i+\max_{j=i}^{2n-1}(T_j-j))+n-1 \]每一个后缀最大值的贡献
首先发现，由于答案的计算式中\(T_j-j\)只会用到后缀最大值，因此我们只需要考虑每个后缀最大值的贡献。
而对于一个后缀最大值，我们要最小化答案就是找到最小的能满足它是后缀最大值的\(i\)，也就是前一个后缀最大值的下标\(+1\)。
要实现这个其实只需要维护出一个从后往前的单调递增的单调栈即可。
线段树维护单调栈
这应该是一个经典操作。
考虑在子节点合并的时候，右子树的单调栈可以直接保留，左子树中则可以通过线段树上二分直接找到大于右子树最大值的最右位置。
为了减少冗余询问，我们在每个节点维护好用右子树最大值在左子树内查询时的结果。
注意虽然\(j\)的范围是\(1\sim 2n-1\)，但\(i\)的范围是\(1\sim n\)，因此\(n\)以后的单调栈其实无法造成贡献。
然后我们发现\(n+1\sim 2n-1\)的最大值其实就是\(1\sim n\)的最大值减\(n\)。
故实际上我们只要维护好\(1\sim n\)的单调栈就可以了。
代码：\(O(nlog^2n)\)
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define INF 1000000000
using namespace std;
int n,a[N+5];
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define pc(c) (C==E&&(clear(),0),*C++=c)
#define D isdigit(c=tc())
int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
public:
I FastIO() {A=B=FI,C=FO,E=FO+FS;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=(x<<3)+(x<<1)+(c&15),D);}
Tp I void writeln(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);pc('\n');}
I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
}F;
class SegmentTree
{
private:
#define PT CI l=1,CI r=n,CI rt=1
#define LT l,mid,rt<<1
#define RT mid+1,r,rt<<1|1
#define PU(x) (Mx[x]=max(Mx[x<<1],Mx[x<<1|1]),T[x]=Find(Mx[x<<1|1],LT))//上传信息
int Mx[N<<2],T[N<<2];
I int Find(CI v,PT)//线段树上二分
{
if(l==r) return Mx[rt]>v?v+l:INF;RI mid=l+r>>1;
return Mx[rt<<1|1]>v?min(T[rt],Find(v,RT)):Find(v,LT);
}
public:
I void Build(PT)//建树
{
if(l==r) return (void)(Mx[rt]=a[l]-l);RI mid=l+r>>1;Build(LT),Build(RT),PU(rt);
}
I void U(CI x,CI v,PT)//单点修改
{
if(l==r) return (void)(Mx[rt]=v);RI mid=l+r>>1;x<=mid?U(x,v,LT):U(x,v,RT),PU(rt);
}
I int Qry() {return Find(Mx[1]-n)+n;}//询问
}S;
int main()
{
RI Qt,Qp,i,x,y,lst;F.read(n),F.read(Qt),F.read(Qp);
for(i=1;i<=n;++i) F.read(a[i]);S.Build(),F.writeln(lst=S.Qry());//初始局面
W(Qt--) F.read(x),F.read(y),Qp&&(x^=lst,y^=lst),S.U(x,y-x),F.writeln(lst=S.Qry());//单点修改
return F.clear(),0;
}