“蔚来杯“2022牛客暑期多校训练营4 E - Jobs (Hard Version)

Jobs (Hard Version)

昨晚 学弟来问我这道题，就浅浅理A了一下

题意：
给定 $n=1e6$ 个公司， $q=2e6$个人，每个公司有$m_i$个岗位，且${\sum }_{i=1}^n{m}_i=1e6$，每个岗位有 $A,B,C$ 三个属性值，每个人有 $a,b,c$ 三个属性值。一个人能够胜任这个岗位，当且仅当$A<=a$ && $B<=b$ && $C<=c$ （$A,a<=400,B,b<=400,C,c<=400$）。试求，对于每个人，他能在几个公司任职。（学弟给的题意，如果错了，请当这篇博客不存在

思路：
如果没有公司的限制，只是要求 每个人能够在几个岗位任职，就是简单的 三维偏序问题，直接 $CDQ$ 即可，但是有公司的限制，就和种类数类似了，不能考虑 $CDQ$ 了。

但是可以借鉴 $CDQ$ 的一些思路，比如，我们可以将所有岗位的 $A,B,C$ 和 人的$a,b,c$ 放在一起，按照 $a,A$ 的大小排序，那么 对于每个人，排在他前面的岗位 就是都满足 $A$ 的条件的（也即 像 $CDQ$ 一样，通过排序降一维）。

这样处理之后，题目就转化成了，序列上 的 pair 对（B,C)，对于每个人$j$，需要求 有多少个公司，满足存在岗位 i，$i<j$ && $B_i<=B_j$ && $C_i<=C_j$ 。因为求的是种类数，将同种类的岗位放在一起看，可以发现，对于两个不同的岗位 $(B,C)$ 和 $(b,c)$ 如果 $B<=b$ 且 $C<=c$ ，那么 $(b,c)$ 是被 $(B,C)$ 包含在内的，可以去掉。也即对于同种类的岗位，有效的岗位是一个 $B$升序，$C$降序的一个单调序列。发现了这个性质，那么离做出来也就不远了。

然后，我们看对于每个人$j$，我们需要求有多少个公司，满足存在岗位 i，$i<j$ && $B_i<=B_j$ && $C_i<=C_j$ ，把 $(B,C)$ 看成是一个平面，也就是求一个点的左下角有多少种类的点。我们可以维护一个 二维树状数组$tr$，$tr[x][y]$ 代表 $(x,y)$ 的左下角的种类数；那么接下来就是怎么维护种类数了，对于每个公司维护一个单调序列，存 $pair$ 的值，那么每次新进来一个 $pair$，可能会让对应单调序列 加入一个点 或者 删除一些点，当然不可能$for$ 单调序列，可以二分出这个 $pair$ 要插入的位置。然后插入一个点或者删除一个点就在 二维树状数组上进行加减，当然不是在当前点的所有右上角进行加减，而是需要求出当前这个点和 单调序列的 前驱、后继 夹出来的特有矩形，在这上面执行操作。这样就能满足 对于一个特定的公司，对于二维平面上每个点 最多只贡献了 1。
对于一个人只需要在全局的二维树状数组 查询一个给定点的值即可。
（懒得画图了，有心人可以自己结合上文 画图理解一下）

复杂度分析：
令$M={\sum }_{i=1}^n{m}_i$；
对于每一个岗位都需要在单调序列中二分一下，因为 $B<=400$，所以单调序列中最多只有 400个点，所以这部分的复杂度是 $M\cdot lo{g}_{2}400$；
对于每个人，都需要在二维树状数组上查询一次值，这部分复杂度是 $q\cdot lo{g}_{2}400\cdot lo{g}_{2}400$。
对于每个岗位在 单调序列上最多只会插入一次、删除一次，所以这部分复杂度是 $M\cdot lo{g}_{2}400\cdot lo{g}_{2}400$
可以发现复杂度是 $O(能过)$ 的，甚至绰绰有余吧。

代码：
因为笔者退役了，代码需要读者自行完成。
当然上面只是口头理A，还有许多细节需要读者自己思考，比如：
因为等式是 $<=$ 的，所以排序之后需要 按照 $B$ 值相等的分组， 先把所有的岗位都插入了，再去求答案。
(如果学弟 写出来了，再把代码贴着吧)

#include
#include
using namespace std;
#define ll long long

int main(){
	
	return 0;
}
1
2
3
4
5
6
7
8
9

碎碎：
昨天晚上理A之后给学弟讲完，也算是感概万千，可能如果不退役，自己也能成为一名出色的金牌选手。
这几天，也不知道自己在纠结什么，不知道是后悔还是不甘，也不知道自己喜欢acm是因为 做出题的愉悦，还是因为自己打的还算不错的底子，抑或是这两年在集训队的点滴。

须知少时凌云志 曾许人间第一流