Luogu

分析

为了方便，把题目里的特征值称为「特征值 A」；再定义一个「特征值 B」表示不弱的 B 的个数。

那么可以将三个问题转化一下：

• 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $k$ 时，请问 X 在哪个位置。
• 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $k-S$ 时，请问 X 在哪个位置。
• 给定密钥中所有 A 的位置，当密钥的特征值 B 为 $S$ 时，请问 X 在哪个位置。

我们随便解决一个即可。

设
$$
a_i=\begin{cases}1,&p_i=\mathsf{A}\\-1,&p_i=\mathsf{B}\lor p_i=\mathsf{X}\end{cases}
$$
再设
$$
s_i=\sum_{j=1}^ia_j
$$
考虑将一个 X 放在位置 $m$，设此时的前缀和数组为 $s_i\!'$，则有
$$
s_i\!'=\begin{cases}s_i-s_m+s_{2k+1},&i<m\\s_i-s_m,&i\geq m\end{cases}
$$
可以发现 $s_{2k+1}=-1$，于是有
$$
s_i\!'=\begin{cases}s_i-s_m-1,&i<m\\s_i-s_m,&i\geq m\end{cases}
$$
一个 B 是不弱的显然应该满足 $s_i\!'<0$，即

• 当 $i<m$ 时，$s_i<s_m+1\Rightarrow s_i\leq s_m$。
• 当 $i\geq m$ 时，$s_i<s_m$。

将两行整合一下，变为
$$
s_i<s_m\lor(s_i=s_m\land i<m)
$$
因此我们对于所有 $p_i\neq\mathsf{A}$ 的位置，拿出一个二元组 $(s_i,i)$，再将所有这些二元组排序。

可以发现，假如 $m$ 为第 $k$ 小的那个二元组的第二维，那么整个密钥的特征值 B 为 $k-1$。

因此我们只需要询问第 $k+1$ 小的二元组、第 $k-S+1$ 小的二元组和第 $S+1$ 小的二元组即可。可以使用 nth_element 做到 $\mathcal{O}(n)$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20000001+10;

int n,k,seed,S,cnt=0;
int a[N],s[N];
pair<int,int> p[N];

inline int rand() { return seed=((seed*12321)^9999)&32767; }
inline void generateData() {
    k=read(),seed=read(),S=read();
    int t=0,i=1; n=k<<1|1;
    for(re int i=1;i<=n;++i) a[i]=(rand()>>7)&1,t+=a[i];
    while (t>k) { while (a[i]==0) ++i; a[i]=0,--t; }
    while (t<k) { while (a[i]==1) ++i; a[i]=1,++t; }
}

inline int query(int k) {
    nth_element(p+1,p+k,p+cnt+1); return p[k].second;
}

int main() { generateData();
    for (re int i=1;i<=n;++i) s[i]=s[i-1]+(a[i]?1:-1);
    for (re int i=1;i<=n;++i)
        if (!a[i]) p[++cnt]=make_pair(s[i],i);
    printf("%d\n%d\n%d\n",query(k+1),query(k-S+1),query(S+1));
    return 0;
}