题解 P4425 【[HNOI/AHOI2018]转盘】
litble
2018-05-04 21:24:43
[你真的不想戳开看一看吗](https://blog.csdn.net/litble/article/details/80187830)
可以发现，如果我需要在转盘上走两圈，不如在第一个物品上停留一段时间，然后再走一圈。
假设我们固定起点，那么一定是走一圈+多出来的一点点。
会发现那多出来的一点点假设走到x，那么以x+1为起点就可以只走一圈。
所以得到结论：**最优方案一定是在第一个物品上停留一段时间后走一圈**。
拆环，把原数列往后面粘一遍，设$a_i=T_i-i$（即走到这里时可以标记该物品需要预先停留的时间），则答案为：
$$\min_{i=1}^n \{ \max_{j=1}^n \{ a_{i+j-1}+i \} \} +n-1$$
也就是：
$$\min_{i=1}^n \{ \max_{j=1}^n \{ a_{i+j-1}\}+i \} +n-1$$
以下将取$\max_{j=1}^n \{ a_{i+j-1}\}+i$的区间称作**“窗口”**，而左边这个取max的式子称作**“窗口的答案”**，注意窗口的长度不一定是n。
用线段树弄一弄。
假设线段树上一个节点代表的区间是$[s,t]$，那么我们开一个数组$mx$表示这个区间内最大的$a_i$，开一个数组$ans$来维护所有包含了整个右半区间的窗口中$\max_{j=1}^n \{ a_{i+j-1}\}+i$的最小值。
这样维护的窗口可能长度会大于n，但是由于在整个长为2n的序列中，有$a_x=T_x-x , a_{x+n}=T_x-x-n$的缘故，如果这个窗口包含了$a_x$，那么$a_{x+n}$及以后的值并不会对该窗口的答案产生影响，所以可以视作所有的窗口长度都是小于等于n的。而每个窗口的长度一定是大于$\frac{t-s+1}{2}$的，所以线段树的根节点，也就是代表区间为$[1,2n]$的那个节点的窗口长度是大于等于n的，综上，我们可以统计所有长度为n的窗口的答案。
然后就是在线段树操作的时候，如何合并左右子区间的答案的问题了。方法和[这道题](https://www.luogu.org/problemnew/show/P4198)差不多，具体实现看代码。
复杂度$O(nlog^2 n+mlog^2 n)$
```cpp
#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
int q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q;
}
const int N=200005;
int n,m,p,lasans;
#define ls (i<<1)
#define rs ((i<<1)|1)
int T[N],a[N],ans[N<<2],mx[N<<2];
//orz:合并左右子区间答案
int orz(int i,int s,int t,int num) {
if(s==t) return s+max(mx[i],num);
int mid=(s+t)>>1;
if(mx[rs]>=num) return min(ans[i],orz(rs,mid+1,t,num));
//此时窗口的左端点在左半时max受的不是num影响，而是右半影响，所以取一次ans[i]
else return min(orz(ls,s,mid,num),mid+1+num);
//否则整个右半作窗口左端点的max都受num影响，左端点越小答案越小。
}
void up(int i,int s,int t) {
mx[i]=max(mx[ls],mx[rs]);
ans[i]=orz(ls,s,(s+t)>>1,mx[rs]);//既然考虑的窗口要包含整个右子区间，则一定包含其a[i]最大值
}
void build(int s,int t,int i) {
if(s==t) {ans[i]=T[s],mx[i]=a[s];return;}
int mid=(s+t)>>1;
build(s,mid,ls),build(mid+1,t,rs),up(i,s,t);
}
void chan(int x,int s,int t,int i) {
if(s==t) {ans[i]=T[s],mx[i]=a[s];return;}
int mid=(s+t)>>1;
if(x<=mid) chan(x,s,mid,i<<1);
else chan(x,mid+1,t,(i<<1)|1);
up(i,s,t);
}
int main()
{
int x,y;
n=read(),m=read(),p=read();
for(RI i=1;i<=n;++i) {
T[i]=read(),T[i+n]=T[i];
a[i]=T[i]-i,a[i+n]=T[i+n]-i-n;
}
build(1,n<<1,1);
lasans=ans[1]+n-1;printf("%d\n",lasans);
while(m--) {
x=read(),y=read();
if(p) x^=lasans,y^=lasans;
T[x]=T[x+n]=y,a[x]=y-x,a[x+n]=y-x-n;
chan(x,1,n<<1,1),chan(x+n,1,n<<1,1);
lasans=ans[1]+n-1;printf("%d\n",lasans);
}
return 0;
}
```
最后，鸣谢[这位dalao](https://www.cnblogs.com/Yuzao/p/8877365.html)对本蒟蒻理解本题的帮助。