E题: Jobs (Hard Version)

原题链接:https://ac.nowcoder.com/acm/contest/33189/E

题目大意

有 $n(1\le n\le 10^6)$ 家公司，第 $i$ 家有 $m_i(1\le m_i\le 10^6,\sum m_i\le 10^6)$ 个工作，每个工作对 $IQ/EQ/AQ(1\le a_j,b_j,c_j\le 400)$ 三项属性各有下限要求。对于某个求职者，如果其满足一家公司的任意一项工作的三维属性要求，则该公司会给他发offer。

有 $q(1\le q\le 2\times 10^6)$ 个求职者，对于每个求职者，求有多少家公司会给他发offer。

询问强制在线。

题解

观察到三维的范围都较小，不妨预处理出 $d{p}_{x,y,z}$ 表示三维分别为 $x,y,z$ 时可收到的offer数。

考虑一个较简单的版本，若只有二维怎么办。
当两个工作 $i,j$ 满足 $a_i\le a_j,b_i\le b_j$ 时，工作 $j$ 被 $i$ 包含，不用考虑。
将互不包含的工作所产生贡献的范围画出图像大致如下:
显然，所有的染色部分都应该做 $1$ 的贡献(因为是同一公司)。
我们不妨进行差分，将每个橙色点 $+1$ ，红色点 $-1$ ，然后横纵各做一次前缀和，即可得到我们想要的结果。

当问题升到三维时，我们可以按照第三维度从小到大枚举每个工作，然后转化为每层一个二维问题。当更上层的工作被包含时，我们不考虑他；如果不被包含，则将被他包含的那些原来的工作的贡献去除。最后做三维前缀和即可(先做第三维度)。
对于判断包含关系，可以将每个工作的前两个维度维护在一个 $set$ 中，因为互不包含的工作在 $a$ 单调增加时， $b$ 单调递减，可以按照顺序进行判断。

参考代码

#include
#include 
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

#define P pair<int,int>
#define X first
#define Y second
const int MAXN=4e2+5,mod=998244353;
int n,q;
int a[MAXN][MAXN][MAXN];
vector<pair<int,P>>v;
set<P>st;

int qpow(int x,int p){// 快速幂(其实seed的幂也可以打表O(q)预处理)
	int ret=1;
	for(;p;x=1ll*x*x%mod,p>>=1)if(p&1)ret=1ll*ret*x%mod;
	return ret;
}

P Next(P p){//寻找后继用于判断是否包含
	return *st.upper_bound(p);
}

int main()
{
	read(n),read(q);
	for(int i=1,m;i<=n;++i){
		read(m);
		vector<pair<int,P>>().swap(v);
		for(int k,x,y;m--;){
			read(k),read(x),read(y);
			v.push_back(make_pair(k,P(x,y)));
		}
		sort(v.begin(),v.end());//先排序
		st.clear();
		st.insert(P(0,401));
		st.insert(P(401,0));//插入两个哨兵节点防止RE
		for(int i=0,k;i<v.size();++i){
			k=v[i].X;
			P p=v[i].Y;
			set<P>::iterator it=st.upper_bound(p);
			--it;//此时的it可能是p的前驱也可能与p相同
			if(it->Y<=p.Y)continue;//p被包含或存在相同
			++a[k][Next(*it).X][it->Y];//将原来的-1贡献消除
			st.insert(p);
			--a[k][p.X][it->Y];//p与前驱的交点-1(因为it不与p相同,则it一定是p的前驱)
			while(Next(p).Y>=p.Y){//包含后继
				P nxt=Next(p);
				--a[k][nxt.X][nxt.Y],++a[k][Next(nxt).X][nxt.Y];//消除后继的贡献
				st.erase(nxt);
			}
			++a[k][p.X][p.Y];//p的贡献
			--a[k][Next(p).X][p.Y];//p与后继的交点
		}
	}
	for(int k=1;k<=400;++k){
		for(int x=1;x<=400;++x){
			for(int y=1;y<=400;++y){
				a[k][x][y]+=a[k-1][x][y];//先处理额外的那个维度
			}
		}
	}
	for(int k=1;k<=400;++k){
		for(int x=1;x<=400;++x){
			for(int y=1;y<=400;++y){
				a[k][x][y]+=a[k][x-1][y];
			}
		}
	}
	for(int k=1;k<=400;++k){
		for(int x=1;x<=400;++x){
			for(int y=1;y<=400;++y){
				a[k][x][y]+=a[k][x][y-1];
			}
		}
	}
	int seed;read(seed);
	std::mt19937 rng(seed);
	std::uniform_int_distribution<>u(1,400);
	int lastans=0,ans=0;
	for(int i=1;i<=q;i++){
		int IQ=(u(rng)^lastans)%400+1;
		int EQ=(u(rng)^lastans)%400+1;
		int AQ=(u(rng)^lastans)%400+1;
		lastans=a[IQ][EQ][AQ];//查表即可
		ans=(ans+1ll*lastans*qpow(seed,q-i)%mod)%mod;
	}
	cout<<ans<<'\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98