C - Make Good
记$sum$为所有数的异或和，$tot$为所有数的和。$tot$显然必须是偶数。所以如果$tot$是奇数的话，就先往数组里面加入一个$1$。
如果$2\times sum > tot$，就往数组里面加入两个${2\times sum - tot \over 2}$，这对数组中的数的异或和没有影响。
否则，先加入一个$2^{58}$（一个很大的$2$的整数次幂），然后就会转化成$2\times sum > tot$的情况。
如果又要加入$1$又要加入$2^{58}$，可以直接加入数$1+2^{58}$，这样就可以满足加的数至多是三个的限制。
D - Strange Device
首先考虑$k=n-1$怎么做：可以把每个大小为$n-1$的子集都问一遍，这样第$m+1$小的会出现$m$次，第$m$小的会出现$n-m$次，根据出现过的元素的大小关系以及它们分别的出现次数就可以推出$m$。
当$n>k+1$，直接对前$k+1$个元素通过上面的方法计算就可以了。
E - Divide Points
将点分成四组：$A_{0,0},A_{0,1},A_{1,0},A_{1,1}$。点$(x,y)$属于组$A_{x\pmod 2,y\pmod 2}$。用$P,Q$代表最后分得的两个点集。
若所有点都属于同一个组，则将所有点的坐标除以$2$（如果原数是奇数，则向下取整）之后再做，与原问题等价。
如果$A_{0,0}\cup A_{1,1}$非空，且$A_{0,1}\cup A_{1,0}$非空，令$P=A_{0,0}\cup A_{1,1},Q=A_{0,1}\cup A_{1,0}$即可。【同一组内的点的$(x+y)\bmod 2$相同】
否则，若$A_{0,0}\cup A_{1,1}$为空集，令$P=A_{0,1},Q=A_{1,0}$即可。【只有同一组内的点的$(x_1-x_2)^2 + (y_1-y_2)^2$是$4$的倍数】
否则$A_{0,1}\cup A_{1,0}$为空集，令$P=A_{0,0},Q=A_{1,1}$。【同上】
F - Awesome Substrings
设$x = {L\over cnt}$，其中$L$表示子串的长度，$cnt$表示子串内$1$的个数。设$T$为某个定值。
设$a_i = \sum_{j\le i} [s_j = 1]$。
将答案分为两部分计算；
- $x\le T$：枚举每一个$x$，然后枚举子串右端点$r$，则左端点应满足${r-(l-1)\over a_r-a_{l-1}} = x\Rightarrow r-a_rx = l-1-a_{l-1}x$，直接用map或者hash_table统计一下即可。
- $x> T$，显然有$cnt = {L\over x} \le {n\over T}$，所以可以枚举子串的左端点和$cnt$，此时要求右端点必须落在某个区间内且$r-l+1 \pmod {cnt}$为$0$，可以$O(1)$计算这样的右端点的数量。
如果用map，时间复杂度$O(nT\log n + n\cdot {n \over T})$，当$T$取${\sqrt{n\over \log n}}$的时候复杂度最优，为$O(n\sqrt {n\log n})$。
G - Subset with Zero Sum
Sol
$i-n\le a_i \le i-1$等价于$1\le i - a_i \le n$。
令$i$向$i-a_i$连边，会得到基环内向树森林。取一个环上的所有元素：
将所有式子加起来，会得到$a_x+a_y+\cdots a_u = 0$。
H - Number of Components
观察发现，如果$i,j(i<j)$连通，那么对于任意的$k\in (i,j)$，$k$与$i,j$连通。
证明：考虑连通块中从$i$到$j$的一条路径，若$k$在这条路径上结论显然成立；否则，这其中必定存在一条边$(u,v)$满足$u < k < v$，由于$a_u < a_v$，所以$a_u < a_k \vee a_k< a_v$一定成立。
所以，连通块一定是序列上的一段连续的区间。
将问题转化成：计算有多少个$p$，满足$[1,p]$和$[p+1,n]$之间没有边。而这个限制条件也等价于$\forall x\in [1,p], y\in [p+1,n], a_x > a_y$。
考虑枚举$[p+1,n]$中的最大值$v$，记序列中小于等于$v$的值为$0$，大于$v$的值为$1$，则$p$合法的条件就是整个序列形如$\overbrace{111\cdots 111}^{\text{p个1}}000\cdots 000$。
发现对于每个$v$而言，它对应的$01$序列是确定的，也就是说尽管一个$v$可以对应多个$p$，但是这些$p$中至多只有一个合法。
所以我们不妨直接统计有多少个$v$对应的$01$序列形如$111\cdots 111000\cdots 000$。
为了方便处理，我们令$a_0 = + \infty, a_{n+1} = -\infty$
用线段树维护对每一个$v$维护它对应的$01$序列中相邻的$10$对的数量，以及$v$是否作为序列中的某个元素出现。由于$10$对的数量至少有一个，所以维护最小值以及最小值的数量，即可得到合法的$v$的数量。