[HNOI/AHOI2018]转盘

题目

洛谷

做法

本文部分为搬运
可以发现，如果我需要在转盘上走两圈，不如在第一个物品上停留一段时间，然后再走一圈。

假设我们固定起点，那么一定是走一圈+多出来的一点点。

会发现那多出来的一点点假设走到(x)，那么以(x+1)为起点就可以只走一圈。

所以得到结论：最优方案一定是在第一个物品上停留一段时间后走一圈。

[ans=min_{1leq i leq n}(max_{0 leq j leq n-1}(t_{i+j}-j)+n-1) ]

[ans=min_{1leq i leq n}(max_{i leq j leq i+n-1}(t_{j}-j+i)+n-1) ]

[ans=min_{1leq i leq n}(max_{i leq j leq i+n-1}(t_{j}-j)+i+n-1) ]

令(x_i=t_i-i)

[ans=min_{1leq i leq n}(max_{i leq j leq i+n-1}x_j+i+n-1) ]

而(x_i=t_i-i,x_{i+n}=t_i-i-n,x_i-n=x_{i+n},x_i>x_{i+n})

[ans=min_{1leq i leq n}(max_{i leq j}x_j+i)+n-1 ]

考虑后缀，最大值是单调的，也就是一个个区间，每个区间显然最小的(i)最优

跟二分一样，找到每个区间的最大(i+1)就是下一个区间的最小(i)，用线段树维护

My complete code

#include<bits/stdc++.h>
using namespace std;
typedef int LL;
const LL maxn=1e6,inf=0x3f3f3f3f;
LL n,m,p,root,nod;
LL w[maxn],mx[maxn],son[maxn][2],T[maxn];
inline LL Query(LL now,LL l,LL r,LL val){
	if(l==r) return mx[now]<=val?inf:l+1+val;
	LL mid(l+r>>1);
	if(mx[son[now][1]]<=val) return Query(son[now][0],l,mid,val);
	else return min(w[now],Query(son[now][1],mid+1,r,val));
}
inline void Update(LL now,LL l,LL r){
	LL lc(son[now][0]),rc(son[now][1]),mid(l+r>>1);
	mx[now]=max(mx[lc],mx[rc]);
	w[now]=Query(lc,l,mid,mx[rc]);
}
void Build(LL &now,LL l,LL r){
	now=++nod;
	if(l==r){
		mx[now]=T[l]-l;
		return;
	}LL mid(l+r>>1);
	Build(son[now][0],l,mid), Build(son[now][1],mid+1,r);
	Update(now,l,r);
}
void Modify(LL now,LL l,LL r,LL x,LL y){
	if(l==r){
		mx[now]=y-l;
		return;
	}LL mid(l+r>>1);
	if(x<=mid)
	    Modify(son[now][0],l,mid,x,y);
	else 
	    Modify(son[now][1],mid+1,r,x,y);
	Update(now,l,r);
}
int main(){
	cin>>n>>m>>p;
	for(LL i=1;i<=n;++i) cin>>T[i];
	for(LL i=1;i<=n;++i) T[i+n]=T[i];
	Build(root,1,(n<<1));
	LL lst;
	cout<<(lst=min(1+mx[root],w[root])+n-1)<<endl;
	while(m--){
		LL x,y; cin>>x>>y;
		if(p) x^=lst,y^=lst;
		Modify(root,1,(n<<1),x,y), Modify(root,1,(n<<1),x+n,y);
	    cout<<(lst=min(1+mx[root],w[root])+n-1)<<endl;
	}return 0;
}