倍长数组(T)。
若从(x)出发，依次标记完所有物品的代价为(n-1+max_{i=x}^{x+n-1}{T_i-(i-x)})，如果某个物品(y)被跳过一次才取到，则取到(y)时的增加的代价/固有时间(n)，而减少的代价/等待时间却不会超过(n)，因为(y)在绕一周之后能够被标记到，总不会减少。这也适用于被跳过多次的情况和跳过多个物品的情况，故称从点(x)出发的最优方案是依次标记完所有的物品。
记(P_i=T_i-i)，根据结论本题的最优解为
[(n-1)+min_{i=1}^n{i+max_{j=i}^{i+n-1}P_j}
]
我有一个(O(2nm))的大胆想法 考虑到(P_i=P_{i+n}+n)，可以变形
[(n-1)+min_{i=1}^n{i+max_{j=i}^{2n}P_j}
]
线段树（总长(2n)，堆式储存）节点(x)维护(m_x=max_{i=l_x}^{r_x}P_i)和(v_x=min_{i=l}^{mid_x}{i+max_{j=i}^{r_x}P_j})，这样答案是
[(n-1)+v_1
]
于(v_x)的合并，设(Q(y)=min_{i=l_y}^{r_y}{i+max_{j=i}^{r_x}P_i})，则
[v_x=min_{i=l}^{mid_x}{i+max_{j=i}^{r_x}P_j}=Q(ls_x)\
]
很显然的有递归式，边界另外看就好了
[Q(y)=egin{cases}
min{v_{y},Q(rs_y)}&m_{rs_y}ge max_{i=r_y+1}^{mid_x}P_i\
min{Q(ls_y),mid_y+1+max_{i=r_y+1}^{mid_x}P_i }&m_{rs_y}<max_{i=r_y+1}^{mid_x}P_i
end{cases}\
]
这样合并(v_x)是一个(log)的，线段树是两个(log)的，完全可行。
代码马上补
代码补好啦
#include <bits/stdc++.h>
#define ll long long
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
int n,q,p,ans,P[N];
int mid[N<<2],m[N<<2],v[N<<2];
int dfn[N<<2];
int Q(int x,int w) {
if(dfn[x]) return dfn[x]+max(m[x],w);
if(m[rs]>=w) return min(v[x],Q(rs,w));
return min(Q(ls,max(w,m[rs])),mid[x]+1+w);
}
inline void upd(int x) {
m[x]=max(m[ls],m[rs]);
v[x]=Q(ls,m[rs]);
}
void build(int x,int l,int r) {
if(l==r) {
m[x]=P[l];
v[x]=l+P[l];
dfn[x]=l;
return;
}
mid[x]=(l+r)>>1;
build(ls,l,mid[x]);
build(rs,mid[x]+1,r);
upd(x);
}
void modify(int x,int l,int r,int p) {
if(l==r) {
m[x]=P[l];
v[x]=l+P[l];
return;
}
if(p<=mid[x]) modify(ls,l,mid[x],p);
else modify(rs,mid[x]+1,r,p);
upd(x);
}
int main() {
scanf("%d%d%d",&n,&q,&p);
for(int i=1; i<=n; ++i) scanf("%d",P+i),P[i+n]=P[i];
for(int i=1; i<=n*2; ++i) P[i]-=i;
build(1,1,n*2);
printf("%d
",ans=n-1+v[1]);
for(int x,y; q--; ) {
scanf("%d%d",&x,&y);
if(p) x^=ans,y^=ans;
P[x]=y-x;
P[x+n]=y-x-n;
modify(1,1,n*2,x);
modify(1,1,n*2,x+n);
printf("%d
",ans=n-1+v[1]);
}
return 0;
}