A
给定序列 \(A\)，构造 \(p_i\)，使得 \(\sum |i-p_i|\) 最小，且 \(B=\{A_{p_i}\}\) 满足奇偶交错出现，且最小化 \(B\) 字典序。
\(n\le 1e5\)。
如果没有最小化字典序，那么我们奇偶分别按照相对顺序分配位置即可。
最小化字典序怎么做呢？我们先把连续的向左或向右的连续段拿出来。
例如最后是连续向右的，那么只要最后还是连续向右的，就可以交换。可能需要数据结构。
B
有 \(n\) 盏灯，初始为熄灭，每盏灯只由一个开关控制，一个开关可以控制多盏灯。
\(q\) 次询问，更改某开关的状态后，极长的亮灯区间有多少个。\(n,q\le 1e5\)。
转化为计算 01 交错的个数除以 2。根号分治秒了。
C
我们发现只有 \(4\) 种不同的树。从结束状态开始往回推，（当前必胜，必败）*（之后必胜，必败）\(4\) 种。
用 \((0/1,0/1)\) 表示，\(0\) 表示输，\(1\) 表示赢。如果有 \((1,1)\) 那么把他放在第一位先手必胜。
逐个分析，如果已经确定后面的状态：
加入 \((0,1)\) 那么状态不会变，且先后手不变，所以这是无用的；加入 \((1,0)\)，状态会改变，先后手交换；
如果有 \((0,0)\)，因为没有 \((1,1)\)，所以无论是先后手只能不断填 \((1,0)\)，否则对方就填 \((0,0)\) 了。
所以如果有 \((0,0)\) 且 \((1,0)\) 为偶数个先手必败。其实，有偶数个 \((0,1)\)，因为最后是 \(0\)，所以一定会输。
所以先手必败的充要条件是：没有 \((1,1)\)，且偶数个 \((1,0)\)。
D
\(n\) 个人之间打循环赛，对于 \((i,j)\) 之间的比赛，其中 \(i<j\)，有 \(p\) 的概率 \(i\) 获胜，\(1-p\) 的概率 \(j\) 获胜。
把这 \(n\) 个人分成两个集合 \(A,B\)，使得 \(A\) 集合里的所有人都战胜 \(B\) 集合的所有人。
对于所有 \(k\)，求 \(|A|=k\) 的概率。\(n\le 1e6\)。
考虑 dp，设 \(F_{n,k}\) 表示当前考虑了 \(n\) 个人，\(|A|=k\) 的概率。
考虑新加一个点，往大的加，那么 \(F_{n+1,k}=p^{k}F_{n,k}+q^{n-k+1}F_{n,k-1}\)。
如果往下的加呢？\(F_{n+1,k}=q^kF_{n,k}+p^{n-k+1}F_{n,k-1}\)，二式相减。
那么 \(F_{n,k}\times(p^k-q^k)=F_{n,k-1}\times (p^{n-k+1}-q^{n-k+1})\)。
那么我们可以 \(O(n)\) 的递推出 \(F_n\)，其中 \(F_{n,0}=1\)，需要特判 \(p=q\) 的情况，这个直接组合数算。