题解 P4425 【[HNOI/AHOI2018]转盘】

· · 题解

题意

给你一个n元环,你可以在0时刻从任意一个位置出发,每一秒可以选择往后或者留在原地

每个点有个参数T_i,当你走到i的时间t\ge T_i时你就可以把i标记

问你把整个环上的点都标记最小需要多长时间,带修改T_i,强制在线

题解

考虑转化问题

假设你t时刻在某个点,每次可以向前走或者留在原地,然后t减1

每个点在T_i时间消失,求一个最小的t使得在所有点都消失前访问所有点

可以发现转化之后你留在原地一定是不优的,也就是说你会一直往前走$

考虑破环为链,枚举一个起点i\in[n,2n),然后往前走到一个点j的时间是t-(i-j)

对于所有的j\in(i-n,i]都要满足

t-(i-j)\ge T_j \Rightarrow t\ge(T_j-j)+i \Rightarrow t_{\min}=\max\{T_j-j\}+i

这样我们就可以枚举i然后在O(n\log n)的时间内求出最优解了

令a_i=T_i-i,那么

Ans=\min_{n\le i\lt 2n}\{\max_{i-n\lt j\le i}a_j+i\}

把i替换成i+(n-1)

\Rightarrow\min_{1\le i\le n}\{\max_{i\le j\le i+n-1}a_j+i\}+n-1

考虑到a_i=T_i-i\gt a_{i+n}=T_i-(i+n),减少一下限制

\Rightarrow\min_{1\le i\le n}\{\max_{i\le j\le2n}a_j+i\}+n-1

对于一个i算出其后缀最大值就可以得到答案,但是这样复杂度不会更优

这时候就要考虑对于一个j来说的答案(令a_0=\inf)

1.$如果$j$就是后缀最大值$,$那么就是找到一个$j$前面第一个权值大于$a_j$的$a_i,$那么答案就是$a_j+i+1

第一点提醒到我们可以从后往前对这个序列维护一个单调上升的栈

假设栈里面的留下的元素是p_0,p_1,\ldots,p_k

其实p_0=0,设j满足p_{j-1}\lt n\le p_j

\Rightarrow Ans=\min_{1\le i\le j}\{a_{p_i}+p_{i-1}+1\}+n-1=\min_{1\le i\le j}\{a_{p_i}+p_{i-1}\}+n

可以用线段树来维护一个单调栈(模板题\to楼房重建)

这里讲一下具体实现和细节

其实就是合并两个区间单调栈的细节

$2.$然后用右子树的区间最大值在左子树里二分找到第一个比其大的位置然后返回答案 对于该位置前面的所有答案取个$\min

记2的一次操作是qry(x)

因为这样是操作是对于一个长度为2n的序列而言的

而最优位置j必须满足p_{j-1}\lt n,所以还需要记录一下上面qry得到的答案

但是我们可以发现对于维护[1,2n]的节点

最后的答案就是(n,2n]里的最大值在[1,n]二分后得到的答案

而(n,2n]里的最大值就是[1,n]里的最大值-n

所以就可以只维护区间[1,n]

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5,inf=1e9;
typedef int arr[N];
int n,m,q,ans,a[N],tr[N<<2],mx[N<<2];
#define lc p<<1
#define rc p<<1|1
int qry(int p,int L,int R,int x){
    if(L==R)return mx[p]>x?x+L:inf;
    int mid=(L+R)>>1;
    return mx[rc]>x?min(tr[p],qry(rc,mid+1,R,x)):qry(lc,L,mid,x);
}
inline void up(int p,int L,int R){
    mx[p]=max(mx[lc],mx[rc]);
    tr[p]=qry(lc,L,(L+R)>>1,mx[rc]);
}
void build(int p,int L,int R){
    if(L==R)return mx[p]=a[L]-L,void();
    int mid=(L+R)>>1;
    build(lc,L,mid),build(rc,mid+1,R),up(p,L,R);
}
void mdy(int p,int L,int R,int x,int w){
    if(L==R)return mx[p]=w-L,void();
    int mid=(L+R)>>1;
    if(x<=mid)mdy(lc,L,mid,x,w);
    else mdy(rc,mid+1,R,x,w);up(p,L,R);
}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n),sd(m),sd(q);
    fp(i,1,n)sd(a[i]);
    build(1,1,n);int x,y;
    we(ans=qry(1,1,n,mx[1]-n)+n);
    while(m--){
        sd(x),sd(y);q?x^=ans,y^=ans:0;
        mdy(1,1,n,x,y),we(ans=qry(1,1,n,mx[1]-n)+n);
    }
return Ot(),0;
}