题解 | #Jobs (Hard Version)#

题目描述

这道题的意思和D题Jobs (Easy Version)大致是一致的，但它之所以称为 hard 是因为的他变量的取值大，即D题擦边过的那些基本不靠谱，下面是中文翻译： alt

分析一波

他要求的是满足公司工作要求得到offer的总数，再进行一段迷惑操作。
如果我们按一个个对比3个值，那怎么看都是TLE的。我们先将他看做D题，将他先用2维表示（三维类似于，这里懒得画doge）
alt 这里看到蓝色的区域被包括了，就是直接被刀了。也不难看出，x足够小就可以存活下来，y足够小也可以存活，z就自己推一下。那么利用差分的方法，我们将图包括的地方标记一下。
alt
这里在极端处表上1，交界处表上-1，因为先根据1的传递（前缀和），防止中间包括的部分被多算，所以减去，即平行于x轴这几条从开端开始一直是1结束至第一个-1，然后为什么后面都是1+(-1)了？因为当你做平行y轴的传递时，最底层的1向上扩散（前缀和）,把0覆盖掉也变成了1，这样就去掉了重复的叠加。至此，只要我们按照图上的x，y，（z）的关系来排序，再标点，查询即可得出有无得到公司的offer。Z轴的话，因为只有400的数据范围，我们可以考虑切层，也就是转化为400个二维的。
由于考虑到不是每一层都要用的，就是n没有那么大而且z也可能相等。所以我们计算的数量可以给出一个式子：

O( n m log m + $c^{3}$ + q)

最后的代码环节

先给出题目自带的代码
In this problem, the IQ, EQ, and AQ of these qq friends are generated as below. First, register an \texttt{mt19937}mt19937 random engine \texttt{rng}rng with the \texttt{seed}seed and a uniform integer distribution object.

#include <random>
std::mt19937 rng(seed);
std::uniform_int_distribution<> u(1,400);

Then, the value of IQ, EQ, and AQ are generated as follows.

int lastans=0;
for (int i=1;i<=q;i++)
{
    int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
    int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
    int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
    lastans=solve(IQ,EQ,AQ);  // The answer to the i-th friend
}

将他扩散成3维

	for(int i=1;i<=400;i++)
		for(int j=1;j<=400;j++)
				for(int k=1;k<=400;k++)
					unv[i][j][k]+=unv[i-1][j][k];
	for(int i=1;i<=400;i++)
		for(int j=1;j<=400;j++)
			for(int k=1;k<=400;k++)
				unv[i][j][k]+=unv[i][j-1][k];
	for(int i=1;i<=400;i++)
		for(int j=1;j<=400;j++)
			for(int k=1;k<=400;k++)
				unv[i][j][k]+=unv[i][j][k-1];

完整代码献上

#include<bits/stdc++.h>
#include <random>
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){//快速幂
	int ret=1;
	for(;p;x=1ll*x*x%mod,p>>=1)if(p&1)ret=1ll*ret*x%mod;
	return ret;
}

P Pre(P p){
	set<P>::iterator it=st.lower_bound(p);
	--it;
	return *it;
}

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));
		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;
			if(it->Y<=p.Y)continue;
			++a[k][Next(*it).X][it->Y];
			st.insert(p);
			--a[k][p.X][it->Y];
			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],--a[k][Next(p).X][p.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-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;
}