[HNOI/AHOI2018] 转盘
倍长数组\(t\)。
若从\(x\)出发,依次标记完所有物品的代价为\(n-1+\max_{i=x}^{x+n-1}\{t_i-(i-x)\}\),如果某个物品\(y\)被跳过一次才取到,则取到\(y\)时的增加的代价/固有时间\(n\),而减少的代价/等待时间却不会超过\(n\),因为\(y\)在绕一周之后能够被标记到,总不会减少。这也适用于被跳过多次的情况和跳过多个物品的情况,故称从点\(x\)出发的最优方案是依次标记完所有的物品。
记\(p_i=t_i-i\),根据结论本题的最优解为
\[
(n-1)+\min_{i=1}^n\{i+\max_{j=i}^{i+n-1}p_j\}
\]我有一个\(o(2nm)\)的大胆想法 考虑到\(p_i=p_{i+n}+n\),可以变形
\[
(n-1)+\min_{i=1}^n\{i+\max_{j=i}^{2n}p_j\}
\]
线段树(总长\(2n\),堆式储存)节点\(x\)维护\(m_x=\max_{i=l_x}^{r_x}p_i\)和\(v_x=\min_{i=l}^{mid_x}\{i+\max_{j=i}^{r_x}p_j\}\),这样答案是
\[
(n-1)+v_1
\]
于\(v_x\)的合并,设\(q(y)=\min_{i=l_y}^{r_y}\{i+\max_{j=i}^{r_x}p_i\}\),则
\[
v_x=\min_{i=l}^{mid_x}\{i+\max_{j=i}^{r_x}p_j\}=q(ls_x)\\
\]
很显然的有递归式,边界另外看就好了
\[
q(y)=\begin{cases}
\min\{v_{y},q(rs_y)\}&m_{rs_y}\ge \max_{i=r_y+1}^{mid_x}p_i\\
\min\{q(ls_y),mid_y+1+\max_{i=r_y+1}^{mid_x}p_i \}&m_{rs_y}<\max_{i=r_y+1}^{mid_x}p_i
\end{cases}\\
\]
这样合并\(v_x\)是一个\(\log\)的,线段树是两个\(\log\)的,完全可行。
代码马上补
代码补好啦
#include <bits/stdc++.h> #define ll long long #define ls (x<<1) #define rs (x<<1|1) using namespace std; const int n=2e5+10; const int inf=0x3f3f3f3f; int n,q,p,ans,p[n]; int mid[n<<2],m[n<<2],v[n<<2]; int dfn[n<<2]; int q(int x,int w) { if(dfn[x]) return dfn[x]+max(m[x],w); if(m[rs]>=w) return min(v[x],q(rs,w)); return min(q(ls,max(w,m[rs])),mid[x]+1+w); } inline void upd(int x) { m[x]=max(m[ls],m[rs]); v[x]=q(ls,m[rs]); } void build(int x,int l,int r) { if(l==r) { m[x]=p[l]; v[x]=l+p[l]; dfn[x]=l; return; } mid[x]=(l+r)>>1; build(ls,l,mid[x]); build(rs,mid[x]+1,r); upd(x); } void modify(int x,int l,int r,int p) { if(l==r) { m[x]=p[l]; v[x]=l+p[l]; return; } if(p<=mid[x]) modify(ls,l,mid[x],p); else modify(rs,mid[x]+1,r,p); upd(x); } int main() { scanf("%d%d%d",&n,&q,&p); for(int i=1; i<=n; ++i) scanf("%d",p+i),p[i+n]=p[i]; for(int i=1; i<=n*2; ++i) p[i]-=i; build(1,1,n*2); printf("%d\n",ans=n-1+v[1]); for(int x,y; q--; ) { scanf("%d%d",&x,&y); if(p) x^=ans,y^=ans; p[x]=y-x; p[x+n]=y-x-n; modify(1,1,n*2,x); modify(1,1,n*2,x+n); printf("%d\n",ans=n-1+v[1]); } return 0; }
上一篇: Mycat的简单配置
下一篇: maven最小配置