SOJ1626 方珍 题解

传送门

题意

给定一个 \(n×n\) 的方阵，其中第 \(i\) 行为 \(A_{i,1},A_{i,2},...,A_{i,n}\)。
对于 \(A_i\) 的所有区间，设 \(f_i\) 为其中第 \(k_i\) 大的 \(mex\) 值。
给定权值序列 \(w_1,w_2,...,w_n\)，求 \(max\{f_i+w_i\}\)。
\(a\) 方阵由给定种子生成。

int n,k,w,m,A[N];
unsigned long long seed;
unsigned long long _rand(){
    seed^=seed<<13;
    seed^=seed>>7;
    seed^=seed<<17;
    return seed;
}
void read_test(){
    scanf("%d%d%d%llu",&k,&w,&m,&seed);
    for(int i=1;i<=n;++i) A[i]=_rand()%m;
}

\(n≤10^4,1≤m≤n,k_i≤\frac{n(n+1)}{2},0≤w_i≤10^9\)

题解

先考虑对每行算出 \(f_i\)。答案具有单调性，可以二分。二分一个 \(mid\)，算出 \(mex\) 大于等于 \(mid\) 的区间个数，与 \(\frac{n(n+1)}{2}-k_i\)比较。
\(mex≥mid\)，则包含 \([1,mid-1]\)。开桶尺取。
时间复杂度 \(O(n^2log n)\)。
另外，实际上我们不需要算出所有\(f_i\)，因为答案仅要求全体最大值。将行按 \(w_i\) 排序，每次从上一步的答案开始判断，正确性易证。
因为答案不超过 \(n\)，故时间复杂度 \(O(n^2)\)。