bzoj3711-[PA2014]Druzyny-分治、线段树优化DP

神仙DP题。

题目链接

题意:给出两个长度为$n$的数列$c$和$d$,让你将$1$至$n$分为连续的几段,保证每段长度$L$满足对于每个属于该区间的元素$i$,$\max(c_i)\leq L\leq\min(d_i)$。问最多分几组,有几种分法能使组数最多,方案数对$10^9+7$取模。

$1\leq n\leq 10^6$

考虑朴素$n^2$DP。

设$f[i]$为前$i$个最多能分$f[i]$组,则转移方程$f[i]=\max(f[j-1])+1,j\in [1,i], \max(c_j,c_{j+1},\ldots,c_i)\leq i-j+1 \leq \min(d_j,d_{j+1},\ldots,d_i)$

考虑如何优化。

令$\rm maxC(j,i)$表示$\max(c_j,c_{j+1},\ldots,c_i)$,$\rm minD(j,i)$表示$\min(d_j,d_{j+1},\ldots,d_i)$。

$\rm maxC(j,i)\leq i-j+1\leq \rm minD(j,i)$

$i-\rm minD(j,i)+1\leq j\leq i-\rm maxC(j,i)+1$

对于左端点$i-\rm minD(j,i)+1$,当$i$不断加大时,易证(不会证感性理解也能出来)左端点只会加大不会减小,具有单调性。因此可以用尺取法(或其他方法)求出对于每一个$i$,能转移到$i$的$j$的左端点为常数,记为$\rm L_i$。

然后考虑右端点,不具有单调性。

由于对于每个$i$,影响其转移右端点的关键因素就是$maxC(j,i)$,所以进行分治。

$solve(l,r)$先在区间$[l,r]$中找出$k$使$c_k$最大,然后递归$solve(l,k-1)$,转移,$solve(k,r)$。

对于当前正在处理的$solve(l,r)$,只考虑左区间$j\in [l,k-1]$对右区间$i\in [k,r]$的转移。此时$\rm maxC(j,i)$为常数$c_k$,记$c_k+1$为$\rm K$。

此时对于$i\in [k,r]$,其转移区间为$[\max(l,\rm L_i),\min(r,i-\rm K)]$。若这个区间为空,则直接跳过。

当$i$递增时,$\rm L_i$递增,$i-\rm K$也递增。所以$i-\rm K<l$或$k-1<\rm L_i$(即区间为空)的$i$只出现在右区间两端,此时无需转移。我们只要考虑转移区间不为空的$i$即可。

同样的,当$\rm L_i$递增时,$i$也在递增。

我们将i分为两个部分:$\rm L_i\leq l$和$l<\rm L_i$。

对于前者,我们只需对$f$建立线段树,然后在线段树上查询第一个$i$的答案。后面的每个$i$只会右移$\min(k-1,i-\rm K)$一次,$O(1)$暴力维护即可(怎么$O(1)$?动动你的小脑浆好好想想)。而且不难发现当$k-1\leq i-\rm K$后,所有$i$的转移区间都是一样的,我们可以直接用线段树区间取$\max$完成转移。复杂度$\log n+\min(k-l,r-k+1)$

对于后者,我们只要在线段树上暴力查询即可。这时肯定会有人出来问我,这复杂度好像不太对啊,成$log^2$了。但实际上,复杂度是均摊$log$的。证明很简单:

对于每个$i$,只有一个$\rm L_i$。对于每一个$i\in [k,r]$的分治层,其$[l,k-1]$的交为空集,并为整个$[1,i-1]$。故$l<\rm L_i\leq k-1$的情况对于每个$i$最多只会出现一次,每次复杂度为$\log n$,总复杂度$n\log n$。

再分析分治复杂度,$T(a+b)=T(a)+T(b)+\min(a,b)+\log n=\rm O(n\log n)$

完美。

不过要注意,此题卡空间,所以各种空间复杂度比较高的数据结构(如ST表)可以用其他空间比较优秀的数据结构代替,用时间换空间。

代码没写,反正卡空间的题写了也会很丑。