[HNOI/AHOI2018]转盘

题目

洛谷

做法

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

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

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

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

\[ans=min_{1\leq i \leq n}(max_{0 \leq j \leq n-1}(t_{i+j}-j)+n-1)\]
\[ans=min_{1\leq i \leq n}(max_{i \leq j \leq i+n-1}(t_{j}-j+i)+n-1)\]
\[ans=min_{1\leq i \leq n}(max_{i \leq j \leq i+n-1}(t_{j}-j)+i+n-1)\]
令\(x_i=t_i-i\)
\[ans=min_{1\leq 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_{1\leq 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;
}

[HNOI/AHOI2018]转盘

原文：https://www.cnblogs.com/y2823774827y/p/10433657.html