YZOJ P2905 [PA2014]Druzyny

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 上来(否则方案数会算重)!

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注