YZOJ P2905 [PA2014]Druzyny

时间限制：1000MS      内存限制：131072KB

难度：\(8.0\)

• 题目描述

在之前的某次校内训练中，zzx 出了一道神奇的题目：给出 \(n\) 个人，要求将所有人分成若干个组，第 \(i\) 个人所在的组的人数必须在 \([l_i, r_i]\) 之间，判断是否存在可行解。

OI组的神犇们决定把这题改造一下：

dick32165401：改成只有编号连续的的一段才可以分一组。

runzhe2000：判定可行解可能会被爆搜水过，最大化分的组数就不那么容易水过了。

E.Space：不仅要最大化组数，还要求出最大化组数的方案数。

ct：数据范围就出100万好了。

于是这题就被这么造好了。

• 输入格式

第一行 \(n\)，\(1 \leq n \leq 1000000\) 。

接下来 \(n\) 行，每行 \(l_i,r_i\)，\(1 \leq l_i \leq r_i \leq 1000000\) 。

• 输出格式

若不存在合法的方案，仅输出一行 \(-1\) 。

否则输出一行两个整数，分别表示组数的最大值和组数取最大值的方案数模 \(10^9+7\) 。

• 样例输入

• 样例输出

 

 

 

Source: BZOJ 3711

膜拜上方所有dalao %%%%%%%%%%%%%%%%%%

像我这种菜鸡看到这种神仙题只会爆零QAQ

---

 

 

 

首先会有一个 DP 方程

\(f_i = \max\limits_{j=0}^{i-1}\{f_j+1\}\)，且 \(\max\limits_{k=j+1}^{i}{c_k} \leq i-j \leq \min\limits_{k=j+1}^{i}{d_k}\)

暴力转移是 \(O(n^2)\) 的，考虑优化。

首先两个限制条件使得本题十分的不可做，考虑去掉其中一个。

注意到 \(i-j \leq \min\limits_{k=j+1}^{i}{d_k}\) ，随着 \(i\) 的增加：\(\min\limits_{k=j+1}^{i}{d_k}\) 是单调不增的，\(i-j\) 是单调递增的，所以满足条件的 \(j\) 的最小值一定是随着 \(i\) 单调不降的。

所以可以先通过双指针法（同时维护一个双端队列）得出 \(g_i\) 表示满足如上条件的 \(j\) 的最小值，并且这里的 \(g_i\) 是单调不降的。

这样就相当于把 \(d\) 的限制去掉了，但是连续的贡献区间会被 \(c\) 的限制切断，所以考虑用一种类似于 CDQ分治 来找到这些连续的贡献区间。

对于分治区间 \([l, r]\) ，找到一个 \(k\) 使得 \([l+1, r]\) 内的 \(c_k\) 最大，考虑用 \([l, k)\) 来贡献 \([k, r]\) 。 

需要特别注意的是，这里不能直接扫 \([l, k)\) 并贡献给 \([k, r]\) ，因为分治的分歧点并不是区间的中点，所以时间复杂度为 \(T(n)=T(k)+T(n-k)+ \cdots\) ，如果 \(O(k)\) 扫一遍的话，复杂度可以是 \(O(n^2)\)，不能达到预期的效果。

要使复杂度得到保证，必须使扫过的元素个数最少，所以用线段树维护区间内 DP 的最大值。

最小可以被贡献到的区间左端点为 \(\max\{k, c_k+l\}\) ，\(i\) 从这里开始，接下来 \(i\) 的向右单调移动（同时 \(g_i\) 单调不降）可以分为以下几种情况：

1，\(g_i < l\) 且 \(i-k < c_k\) 。这意味着并不是 \(\forall j \in [l, k)\) ，都有 \(i-j \geq c_k\) 。所以必须采用双指针法，对于每次 \(i\) 的单调移动，\(j\) 也随之单调右移，并把满足条件的合法最大 DP 值贡献给 \(i\) 。

2，\(g_i < l\) 且 \(i-k \geq c_k\) 。这意味着 \(\forall j \in [l, k)\) ，都有 \(i-j \geq c_k\) ，即 \([l, k)\) 中所有的 DP 值都可以贡献给 \(i\) 。并且更好的是，随着 \(i\) 单调右移，这个性质仍然不会改变，即 \([l, k)\) 中的所有 DP 值都可以贡献给 \(i\) 单调右移形成的一个连续的区间。

具体的来说，设 \(pos\) 为第一个使得 \(g_{pos} \geq l\) 的下标，那么 \(pos\) 之前符合条件的 \(i\) 都可以由 \([l, k)\) 贡献而来，即 \([l, k)\) 可以贡献给区间 \([i, pos)\) 。所以先在线段树上查询区间 \([l, k)\) 中的最大 DP 值，然后在 \(g\) 上二分出 \(pos\)，最后再在线段树上区间更新 \([i, pos)\) 的最大 DP 值。此时，\(i\) 从 \(pos\) 开始继续右移，即转到了情况 3 或 4 。

3，\(g_i \geq l\) 且 \(g_i < k\) 。可以发现对于当前的 \(i\) ，能贡献给它的区间为 \([g_i, \min\{k-1,i-c_k\}]\) 。直接在线段树上区间查询，然后更新即可即可。

4，\(g_i \geq k\) ，没有能贡献给 \(i\) 的区间了，退出。

按照 CDQ分治 的那一套，首先应该先进入 \([l, k-1]\) ，然后再处理贡献，最后再进入 \([k, r]\) ，所以处理贡献时左区间的 DP 值已经全部被求出来 并且保存在线段树上，保证了上面的分类讨论是正确的。

现在来分析一下复杂度。

对于 2 操作，显然每个分治区间只会出现一种这样的情况，所以总时间复杂度为 \(O\left(n\log n\right)\) 。

对于 3 操作，对于每一个 \(i \in [k,r]\) 的分治层，其 \([l, k)\) 的交为空集，并为整个 \([1, i)\) 。故 \(g_i \geq l\) 且 \(g_i < k\) 的情况对于每个 \(i\) 最多只会出现一次，所以总时间复杂度为 \(O\left(n\log n\right)\) 。

对于 1 操作，由于 \(i\) 和 \(j\) 都是单调右移的，所以单次只会移动 \(O\left(\min\{k-l, r-k\}\right)\) ，根据启发式合并的那一套理论，时间复杂度保持在 \(O\left(n \log n\right)\) 。

所以分治的总时间复杂度为 \(T(n)=T(k)+T(n-k)+\min\{n,n-k\}+\log n= O\left(n\log n\right)\) 。

这样就成功把复杂度降下来了，注意常数的话就可以通过本题。

需要注意的地方：

1，毒瘤卡空间，ST 表开不下，线段树维护 \(c\) 区间最大值的时候竟然爆栈了，改成zkw线段树或者用笛卡尔树把分治改成非递归的即可。

2，注意，转移贡献的时候组数要 \(+1\) （正常人都不会忘吧

3，在分治区间 \(l=r\) 的时候需要更新 DP 值以及线段树，注意先从线段树中取出最大值来更新 f 数组，然后再塞回线段树中。注意这里的单点修改不能打 lazy_tag ，必须直接修改叶子结点的值然后再 PushUp 上来（否则方案数会算重）！