题解：密码特征值与X位置的映射

问题转化

已知$n=2k+1$个位置排成环，其中$k$个位置是A（集合$P$），$k$个位置是B，1个位置是X。

定义：从X顺时针出发，到某个A时，若途中A的个数严格大于B的个数，则称该A为“强的”。特征值=强的A的个数。

给定A的位置（即集合$P$），有$k+1$种放置X的位置（对应$k+1$个空位），特征值恰好取遍$0,1,\dots,k$。

需要根据特征值反推X的位置。

关键概念

1. 序列表示

将环从X断开，按顺时针展开为长度为$2k$的序列（不含X）。
令A对应$+1$，B对应$-1$，得到一个长度为$2k$的序列$s_1,s_2,\dots,s_{2k}$，其中$+1$有$k$个，$-1$有$k$个。

2. 前缀和与强的A

设前缀和$pre_i = s_1 + s_2 + \dots + s_i$。

从X出发顺时针到第$j$个A（按遇到顺序）时，设该A在序列中的位置为$t$，则途中A的个数严格多于B的个数 ⇔ 到达该A时的前缀和$pre_t > 0$。

因此，强的A的个数就是所有A位置中满足$pre_t > 0$的个数。

3. 不同断点对应不同特征值

当X的位置移动时，序列循环移位。设原序列（固定某个参考X）为$s_1,\dots,s_{2k}$，前缀和为$pre_i$。

若X顺时针移动$d$步（即原序列向右循环移位$d$），则新序列为$s_{d+1},\dots,s_{2k},s_1,\dots,s_d$。

新前缀和$pre'_i = pre_{d+i} - pre_d$（对$i \le 2k-d$）或$pre'_i = pre_{i-(2k-d)} + (pre_{2k} - pre_d)$（对$i > 2k-d$）。

但注意$pre_{2k}=0$（因为$+1$和$-1$数量相等），所以$pre'_i = pre_{(d+i)\bmod 2k} - pre_d$（模$2k$下标，且$pre_0=0$）。

因此，新序列中位置$t$的符号为$+1$时，条件是$pre_{(d+t)\bmod 2k} - pre_d > 0$。

4. 转化为找第S大的断点

问题变为：给定$pre_1,\dots,pre_{2k}$，求一个偏移$d$（$0\le d < 2k$，且$d$对应一个B或A的位置？实际上$d$对应原X后的位置索引），使得满足$pre_{(d+t)\bmod 2k} - pre_d > 0$的$t$个数（其中$s_{(d+t)\bmod 2k}=+1$）等于$S$。

由于$d$取$k+1$个特定值（对应X在某个非A位置？不，X可以在任何位置，但给定A的位置时，X只能放在非A位置，有$k+1$个空位）。

实际上，$d$对应X在原序列中的“前一个位置”索引。设原序列$s_1,\dots,s_{2k}$对应某个参考X（比如放在位置1之前）。则X实际在位置$i$之前（$i=1,\dots,2k+1$）对应偏移$d=i-1$（模$2k$），但需保证$i$不是A的位置（因为X不能与A重叠）。

5. 特征值0对应X的位置

特征值0表示没有强的A，即对所有A位置$t$，$pre_{(d+t)\bmod 2k} - pre_d \le 0$。

由于$pre$是整数且变化量为±1，这等价于$pre_{(d+t)\bmod 2k} \le pre_d$对所有A位置$t$成立。

这要求$pre_d$是$pre$在所有A位置索引上的最大值？不，是$pre_d \ge \max_{t \in A} pre_t$？但$pre$可能重复。

实际上，令$M = \max_{t \in A} pre_t$，需要$pre_d \ge M$？但若$pre_d = M$且某个A位置$t$满足$pre_t = M$，则差为0，不满足严格大于0，所以该A不强。因此特征值0的条件是：$pre_d \ge \max_{t \in A} pre_t$，且取等时该A不算强。

但更精确地：对所有A位置$t$，$pre_{(d+t)\bmod 2k} \le pre_d$。

由于序列循环，可重新标号使X在位置0（即偏移$d=0$），那么$pre_t \le 0$对所有A位置$t$成立。

因此问题转化为：找到一个循环移位，使得所有A位置的前缀和$\le 0$。

6. 已知结论

由题目结论，特征值$S$与X的位置一一对应，且特征值$S$等于“从X顺时针出发，第一次遇到前缀和达到某个值的次数”等。

实际上，若将$pre$值看作高度，从X出发（高度为$pre_d$），顺时针走，遇到A时检查当前高度是否大于出发高度。强的A的个数就是高度严格大于出发高度的A的个数。

因此，将所有位置按$pre$值排序，特征值$S$对应选择第$S+1$高的出发高度？但需考虑A的位置。

7. 特征值S的X位置

更系统的方法： 定义数组$pre[0..2k]$，$pre[0]=0$，$pre[i]=pre[i-1]+s_i$，其中$s_i=+1$如果位置$i$是A，否则$-1$。

环上位置从1到$2k+1$，X放在位置$pos$（$1\le pos\le 2k+1$）时，对应断点在$pos-1$（模$2k$），即偏移$d = pos-1$。

设$h = pre_d$（出发高度）。

强的A的个数 = #{ $t \in A$ | $pre_t > h$ }（在循环意义下，$pre_t$是$t$位置的前缀和，注意$t$索引可能大于$d$需调整）。

因为循环移位后，位置$t$的新前缀和为$pre_t - h$（若$t>d$）或$pre_t + pre_{2k} - h = pre_t - h$（因为$pre_{2k}=0$）。所以确实就是$pre_t > h$的A的个数。

因此，特征值$S$对应选择$h$使得恰好有$S$个A位置满足$pre_t > h$。

8. 具体算法

预处理：

• 给定A的位置集合$P$（大小为$k$）。
• 构造序列$s[1..2k]$，对应位置$1..2k$为A（+1）或B（-1），位置$2k+1$留给X？注意环上共$2k+1$个位置，但我们构造序列时先固定X在位置$2k+1$，则序列$s_1..s_{2k}$对应位置$1..2k$的值。
• 计算前缀和$pre[0..2k]$，$pre[0]=0$，$pre[i]=pre[i-1]+s_i$。
• 记录所有A位置（在$1..2k$中）的$pre$值，记为集合$H_A$。
• 对$H_A$排序。

对于特征值$S$： 我们需要$h$使得#{ $x \in H_A | x > h$ } = $S$。 由于$S$从0到$k$，$h$应取$H_A$中第$k-S$大的值？不，#{ $x > h$ } = $S$ ⇒ 有$S$个大于$h$，$k-S$个小于等于$h$。所以$h$是$H_A$中第$k-S$小的值？不，若$h$等于某个$H_A$值，则相等的不算大于，所以$h$应介于$H_A$中第$k-S$大和第$k-S+1$大之间？但$h$必须是某个$pre_d$值（$d=0..2k$）。

实际上，$h = pre_d$，$d$是某个位置索引（0..2k）。我们需要#{ $t \in A | pre_t > pre_d$ } = $S$。

因此，对每个$d$（0..2k），计算$c(d) =$ #{ $t \in A | pre_t > pre_d$ }。 则$c(d)$取遍0..k，且一一对应。

我们需要：

• 特征值0：$c(d)=0$ ⇒ $pre_d \ge \max_{t\in A} pre_t$。
• 特征值S：$c(d)=S$ ⇒ $pre_d$是使得恰好$S$个$pre_t$大于它的值。

因此，将所有$pre_d$（$d=0..2k$）排序，并与$H_A$比较，即可得到每个$c(d)$。

9. 位置映射

$d$对应X在位置$d+1$（若$d<2k$）或位置$2k+1$（若$d=2k$？注意$d$范围0..2k-1对应位置1..2k，$d=2k$对应位置$2k+1$？但$pre[2k]=0$，且位置$2k+1$是X）。

但注意：$d$是序列索引（0..2k-1）对应位置$d+1$是X？不，若$d$是前缀和索引，则$d$对应在位置$d$之后放X（即X在位置$d+1$，环上模$2k+1$）。

更准确：设位置1..2k+1，序列$s_1..s_{2k}$对应位置1..2k，位置$2k+1$是X（参考）。那么$pre[i]$对应位置$i$（i=1..2k）的前缀和。X放在位置$pos$时，相当于将环旋转使$pos$成为新起点，则新序列的前缀和是原$pre$减去$pre[pos-1]$（模意义）。因此$h = pre[pos-1]$（若$pos=2k+1$，则$h=pre[2k]=0$）。

因此，$d = pos-1$，$d=0..2k$（$d=2k$对应$pos=2k+1$）。

10. 答案计算步骤

1. 给定A的位置集合$P$（大小为$k$）。

2. 构造数组$s[1..2k]$：对$i=1..2k$，若$i \in P$则$s[i]=1$，否则$s[i]=-1$。

3. 计算$pre[0..2k]$：$pre[0]=0$，$pre[i]=pre[i-1]+s[i]$（$i=1..2k$）。

4. 收集所有$pre[t]$（$t \in P$）到数组$H_A$，排序。

5. 对$d=0..2k$，计算$c(d) =$ #{ $x \in H_A | x > pre[d]$ }。

   • 可通过排序所有$pre[d]$并与$H_A$比较得到。

6. 建立映射$f: c(d) \rightarrow pos = d+1$（若$d<2k$）或$pos=2k+1$（若$d=2k$）。

   • 注意：$pos$不能是A的位置，需检查$pos \notin P$。但$d=2k$对应$pos=2k+1$肯定不在$P$（因为$P \subseteq \{1..2k\}$）。对于$d<2k$，若$pos=d+1 \in P$，则这个$d$不可行（因为X不能放在A上）。所以实际上$d$只能取$pos-1$且$pos \notin P$。
   • 因此需要过滤：$d$满足$d+1 \notin P$（且$d \le 2k$）。
   • $d=2k$时$pos=2k+1$自动满足。

7. 对于特征值S：

   • 第一问：$S=0$，找$c(d)=0$且$d+1 \notin P$的$pos=d+1$。
   • 第二问：$S$，找$c(d)=S$且$d+1 \notin P$的$pos=d+1$。
   • 第三问：给定B的位置（即$P$是B的位置），则A的位置是补集。同样计算，只需将$s[i]$符号取反？不，只需将$H_A$改为A位置的$pre$值（A位置是$P$的补集）。

11. 时间复杂度

• 构造$pre$：$O(k)$
• 排序：$O(k \log k)$
• 映射：$O(k)$ 总复杂度$O(k \log k)$，可过$k\le 10^7$（需注意内存和常数）。

12. 具体实现

• 用数组存储$pre$和位置信息。
• 用计数排序或快速排序。
• 注意$k$很大，避免递归爆栈。

13. 第三问转换

给定B的位置集合$P_B$（大小$k$），则A的位置是补集$P_A = \{1..2k\} \setminus P_B$。 算法同上，只需将$H_A$改为$P_A$的$pre$值集合。

14. 最终输出

对每个询问，输出对应的$pos$即可。