题解 CF573B 【Bear and Blocks】

这道题听说可以采用曼哈顿最小生成树的$\Theta(n \log_2n)$算法，不过这里不讨论。我们来讲一下如何使用线段树维护。 ------------ 读完题目之后，我们很容易发现，最后消失的那几个方块至少有一个一定位于最底层（因为它上面的方块一定不会比它后消除）。所以我们设每个“塔”的高度为$h_i$，那么我们会发现第一次操作的时候它的高度就是$\min(h_i-1,h_{i-1},h_{i+1})$。不过因为 这个转移它有后效性，不能直接DP/递推得出答案。所以我们考虑如下递推式：我们递推第$k$次在第$i$座“塔”上操作后的高度，则$$h_i=\max(0,\displaystyle\min_{j=0}^{i}\{\min(h_{i-j},h_{i+j})-(k-j)\})$$ 我们发现这个式子需要枚举$i$和$j$，复杂度不符合要求，怎么办呢？ 观察发现，我们这里因为$k$是一个常数，不影响最优性；也就是说，我们要求的是$\displaystyle\min_{j=0}^{i}\{h_{i-j}+j\}$和$\displaystyle\min_{j=0}^{i}\{h_{i+j}+j\}$，也就是两个区间最值。于是，我们就使用线段树维护这个东西。 ------------ 这样，我们就在$O(n\log_2n)$的时间内完成了递推，最后对于每一个$i$，我们就可以求出把这堆删除的最小时间。我们把答案取$\max$即可。代码如下： ```cpp #include<cstdio> #include<cstring> int min(int x,int y) { return x<y?x:y; } int max(int x,int y) { return x>y?x:y; } class seg_tree { private: static const int MAXN=100010; struct node { int l,r,val; int lazy; }tree[MAXN<<2]; void upd(int o) { tree[o].val=min(tree[o<<1].val,tree[o<<1|1].val); } void pushdown(int o) { int tmp=tree[o].lazy; tree[o].lazy=0; if(tmp) { tree[o<<1].lazy+=tmp; tree[o<<1|1].lazy+=tmp; tree[o<<1].val+=tmp; tree[o<<1|1].val+=tmp; } } public: int ord[MAXN]; void build(int o,int l,int r) { tree[o].l=l; tree[o].r=r; tree[o].lazy=0; int mid=(l+r)>>1; if(l==r) { tree[o].val=ord[l]; return; } build(o<<1,l,mid); build(o<<1|1,mid+1,r); upd(o); } void update(int o,int lt,int rt,int v) { int l=tree[o].l,r=tree[o].r; int mid=(l+r)>>1; if(lt<=l&&r<=rt) { tree[o].val+=v; tree[o].lazy+=v; return; } pushdown(o); if(lt<=mid&&rt>=l) update(o<<1,lt,rt,v); if(lt<=r&&rt>mid) update(o<<1|1,lt,rt,v); upd(o); } int query(int o,int lt,int rt) { int l=tree[o].l,r=tree[o].r; int mid=(l+r)>>1; if(lt<=l&&r<=rt) return tree[o].val; pushdown(o); int res=2147483647; if(lt<=mid&&rt>=l) res=min(res,query(o<<1,lt,rt)); if(lt<=r&&rt>mid) res=min(res,query(o<<1|1,lt,rt)); return res; } }; seg_tree sol; int lans[100010],rans[100010]; int read() { int res=0;char ch=getchar(); while(ch>='0'&&ch<='9') { res=(res<<3)+(res<<1)+ch-'0'; ch=getchar(); } return res; } int main() { int n=read();; for(int i=1;i<=n;i++) sol.ord[i]=read(); sol.build(1,0,n+1); for(int i=1;i<=n;i++) { sol.update(1,0,i-1,1); lans[i]=sol.query(1,0,i); } sol.build(1,0,n+1); for(int i=n;i;i--) { sol.update(1,i+1,n+1,1); rans[i]=sol.query(1,i,n+1); } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,min(lans[i],rans[i])); printf("%d\n",ans); return 0; } ```