【BZOJ5286】[HNOI2018]转盘（线段树）
题面
题解
很妙的一道题目啊。（全世界除了我这题都有40分，就我是一个状压选手
首先来发现一些性质，我们走一圈一定不会更差。 为啥呢？我们反过来看，我们可以钦定一个时间\(T\)，然后从这个时刻出发，每个时刻可以向前走一步或者停留于此，而每个物品有一个消失时间，过了这个时间你还没有到这个位置你就凉了。 那么我们发现我们显然只需要走一圈就可以拿到所有的东西，如果走一圈还有东西拿不到那你走再多圈也拿不到。 那么现在我们要做的就是让钦定的时间\(T\)最短，那么我们又发现了，你显然不会停，停下来显然不优，因为我们现在要做的就是走一圈，既然所有东西都会消失，那么停下来干啥啊。 行，那么我们再正回来，也就是两个性质：只要我们开始走了，我们就不会停，要停也只会在起点停留若干时间之后一直向前走。另外一个是，我们只会走一圈，走回起点的前一个格子就结束了。 所以，不难发现我们的答案就是停留时间加上\(n-1\)。 考虑为啥要停留，证明有一个物品出现的时间很晚，我们必须要在所有物品出现以后才能拿。 那么这个出发时间是什么呢？假设物品的位置是\(j\)，出发点是\(i\)，\(j\ge i\)，物品出现的时间是\(t\)。假设我们等待的时间是\(x\)。那么显然\(x+j-i\ge t_j\)，移项可以得到\(x\ge t_j-j+i\)，也就是\(x=max(j-i+t_j)\)，写得好看点就是\(x=max(t_j-j+i)\)。 那么我们要求的答案就是\((n-1)+min_{i=1}^nmax_{j=i}^{n+n}t_j-j+i\) 为什么要到\(n+n\)我们破环成链之后再原数组后面再接了一份。至于为什么不是到\(i+n\)是因为\(i+n+1\)到\(n+n\)这一段一定不会出现最大值。 现在考虑这个东西怎么维护就好了。 不难发现可能的最大值一定是一个关于\(t_j-j\)的单调栈。维护单调栈可以参考楼房重建那题。 大致的做法是，令\(mx\)表示区间的\(t_j-j\)的最大值。\(ans\)表示区间的答案。 考虑如何合并两个区间，这个东西是一个后缀区间的单调栈，所有右区间的值是直接拿过来用的。 考虑左区间接过来的答案，我们记录当前的右区间的最值，在左区间上面进行二分，找到最后一个大于最值的位置，那么单调栈我们就一直了，那么答案只需要沿着二分区间一路取\(max\)就可以了。 时间复杂度两个\(log\)。#include#include using namespace std;#define MAX 200200#define lson (now<<1)#define rson (now<<1|1)inline int read(){ int x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}int n,m,typ,T[MAX],lans;int t[MAX<<2],mx[MAX<<2];int Query(int now,int l,int r,int x){ if(l==r)return l+max(x,mx[now]); int mid=(l+r)>>1; if(mx[rson]>=x)return min(t[now],Query(rson,mid+1,r,x)); return min(Query(lson,l,mid,x),mid+1+x);}void pushup(int now,int l,int r){ int mid=(l+r)>>1; t[now]=Query(lson,l,mid,mx[rson]); mx[now]=max(mx[lson],mx[rson]);}void Build(int now,int l,int r){ if(l==r){t[now]=T[l];mx[now]=T[l]-l;return;} int mid=(l+r)>>1; Build(lson,l,mid);Build(rson,mid+1,r); pushup(now,l,r);}void Modify(int now,int l,int r,int p){ if(l==r){t[now]=T[l];mx[now]=T[l]-l;return;} int mid=(l+r)>>1; if(p<=mid)Modify(lson,l,mid,p); else Modify(rson,mid+1,r,p); pushup(now,l,r);}int main(){ n=read();m=read();typ=read(); for(int i=1;i<=n;++i)T[i]=T[i+n]=read(); Build(1,1,n+n);printf("%d\n",lans=t[1]+n-1); while(m--) { int x=read(),y=read();if(typ)x^=lans,y^=lans; T[x]=T[x+n]=y;Modify(1,1,n+n,x);Modify(1,1,n+n,x+n); printf("%d\n",lans=t[1]+n-1); } return 0;}