显然最优走法是先一直停在初始位置然后一次性走完一圈。将序列倍长后，相当于找一个长度为n的区间[l,l+n)，使其中ti+l+n-1-i的最大值最小。容易发现ti-i>ti+n-(i+n)，所以也就相当于是后缀最大值最小。设ti-i=ai，即要求min{l+max{al..2n}}+n-1 (l=1..n)。如果没有修改的话只要扫一遍就行了。
线段树看起来很难维护，考虑分块。每一块求出仅考虑该块的ai时上述值的前缀min和ai的后缀max。对于查询，从后往前考虑所选区间左端点在哪一块。如果该块某个位置出现了整个序列的后缀最大值，序列后面的部分就不会对该块之前位置的答案产生影响，可以直接使用之前求出的答案。于是根据后缀最大值将该块划分成两部分，后一部分由于max{ai}被固定为后缀最大值，当然选择尽量左的点时最优。修改时暴力重构块即可。块大小取nsqrt(nlogn)时最优，为O(msqrt(nlogn))。没有卡常也在慢如狗的bzoj上只跑了11s。
事实上这个做法可以扩展到线段树上。待补。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 200010 #define inf 2000000010 char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)&&(c<‘0‘||c>‘9‘)) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();} while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,op,a[N],L[N],R[N],pos[N],mx[N],mn[N],block,num,ans=inf; void build(int x) { mx[R[x]]=a[R[x]];mn[R[x]]=R[x]+a[R[x]]; for (int i=R[x]-1;i>=L[x];i--) mn[i]=i+(mx[i]=max(mx[i+1],a[i])); for (int i=L[x]+1;i<=R[x];i++) mn[i]=min(mn[i-1],mn[i]); } int query() { int u=-inf,ans=inf; for (int i=2*num;i>num;i--) u=max(u,mx[L[i]]); for (int i=num;i>=1;i--) { int l=L[i],r=R[i],x=R[i]+1; while (l<=r) { int mid=l+r>>1; if (mx[mid]<=u) x=mid,r=mid-1; else l=mid+1; } ans=min(ans,x+u);if (x>L[i]) ans=min(ans,mn[x-1]); u=max(u,mx[L[i]]); } return ans; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj5286.in","r",stdin); freopen("bzoj5286.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif n=read(),m=read(),op=read();block=sqrt(n*log(n+1));num=(n-1)/block+1; for (int i=1;i<=n;i++) a[i]=a[i+n]=read(); for (int i=1;i<=n*2;i++) a[i]-=i; for (int i=1;i<=num;i++) { L[i]=R[i-1]+1,R[i]=min(n,L[i]+block-1); for (int j=L[i];j<=R[i];j++) pos[j]=i; build(i); } for (int i=num+1;i<=2*num;i++) { L[i]=R[i-1]+1,R[i]=min(2*n,L[i]+block-1); for (int j=L[i];j<=R[i];j++) pos[j]=i; build(i); } ans=query()+n-1;cout<<ans<<endl; while (m--) { int x=read()^ans*op,y=read()^ans*op; a[x]=y-x,a[x+n]=y-x-n;build(pos[x]),build(pos[x+n]); printf("%d\n",ans=query()+n-1); } return 0; }
BZOJ5286 HNOI/AHOI2018转盘（分块/线段树）
原文：https://www.cnblogs.com/Gloid/p/10113368.html