, ,
,以及
相关题目：可以发现转化之后你留在原地一定是不优的 , 也就是说你会一直往前走 , 其实区别在于开始的时间
比如原来的最优解为\(a=\{ 1,2,3,6,7 \}\) 可以转化为 \(a=\{3,4,5,6,7\}\)枚举出发时间\(t\)和出发点\(i\) , 枚举等待时间最长的点\(j\) , 则有\[ans=min_i\{max\{T_j-(j-i)\}+n-1\}\]
设\(x_i=T_i-i\) , 即\[ans=min_i\{max\{x_j\}+i\}+n-1\]
又有\(x_j>x_{j+n}\) , 所以\(x_{j+n}\)对枚举最大值不会有影响 , 线段树上询问的范围也就可以从\([i,i+n-1]\)换为\([i,2n]\)
线段树维护单调栈结构 , 记\(mx[i] = max\{T_j-j \} , ans[i] = min\{max\{T_j-j\}+i\}\)非常好的题 , 代码也很值得推敲 , 非常值得借鉴
具体细节见代码维护单调栈的信息时维护整个区间非常不好搞 , 可以只维护一半的信息 , 另一半通过动态的比较得出 往左边继续找的时候 , 要记得比一下右边的答案 ; 往右边继续找的时候 , 要记得比一下左边的答案 ; 注释更新于\(19.3.31\)#include#include #include #include #define debug(...) fprintf(stderr,__VA_ARGS__)#define Debug(x) cout<<#x<<"="< < 57){if(c=='-')f=-1;c=getchar();} while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar(); return f*x;}const int MAXN=2e5+5;int a[MAXN];int n,m,type,lastans;struct SGT{// ans[i] = min{ max{ Tj-j } + i } 定义为在左儿子中的答案// mx[i] = max{ Tj-j }//这里懒得卡什么空间之类的,枚举范围直接到2n,方便想,反正也不会错 int ans[MAXN<<2],mx[MAXN<<2];#define ls (rt<<1)#define rs (rt<<1|1) //要求min{max{Xj}+i},所以i要尽可能小,所以维护一半信息的话就应该是把右边的参数传到左边 //还是当做模板记下来吧... inline int query(int rt,int l,int r,int tmp){//得到上一层区间左半边的答案 //核心:用到tmp或者把tmp继续往下传 if(l==r) return l+max(mx[rt],tmp);//特判长度为1:必须根据定义 int mid=(l+r)>>1; //直接返回答案也变成了直接传一半的参到另一半 if(mx[rs]>=tmp) return min(ans[rt],query(rs,mid+1,r,tmp));//右边的mx更大,可能答案在右边,但也要记得比较左边的答案ans[rt] else return min(query(ls,l,mid,tmp),tmp+mid+1);//应该往左边找,而右边的答案是tmp+mid+1(已经判过tmp>mx[rs]) } inline void pushup(int rt,int l,int r,int mid){ //维护最值的写法:直接把一半的参传到另一半去比较,维护某个半边的答案,这样才能做到另半边能够动态的比较得出 ans[rt]=query(ls,l,mid,mx[rs]); mx[rt]=max(mx[ls],mx[rs]);//mx[]很好更新 } inline void build(int rt,int l,int r){ if(l==r){ ans[rt]=a[l]; mx[rt]=a[l]-l; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); pushup(rt,l,r,mid);//非常骚的线段树维护单调栈结构的pushup() } inline void modify(int rt,int l,int r,int x){ if(l==r){ ans[rt]=a[l]; mx[rt]=a[l]-l; return; } int mid=(l+r)>>1; if(x<=mid) modify(ls,l,mid,x); else modify(rs,mid+1,r,x); pushup(rt,l,r,mid); }#undef ls#undef rs}T;int main(){ n=read(),m=read(),type=read(); for(int i=1;i<=n;i++) a[i]=a[i+n]=read(); T.build(1,1,n<<1); printf("%d\n",lastans=T.ans[1]+n-1); for(int i=1;i<=m;i++){ int x=read(),y=read(); if(type) x^=lastans,y^=lastans; a[x]=a[x+n]=y; T.modify(1,1,n<<1,x); T.modify(1,1,n<<1,x+n); printf("%d\n",lastans=T.ans[1]+n-1); }}
\(19.3.21\)