How to AK ABC306
A
题意：吧字符串的每个字符连续输出两遍，记得不要快读，不要忘记输入 $ n $
纪念 Qinzh A 题 WA 掉
B
题意：给定长度为 $ 64 $ 的数组 $ A $，输出 $ \sum_{i = 0}^{63} A_i2^i $
暴力模拟即可
注意要开 unsigned long long
纪念我 WA 了 $ 2 $ 次，第一次用的 int，第二次 long long，第三次 unsigned long long AC
C
题意：给定一个数组 $ A $，里面每个数出现 $ 3 $ 次
把每个数第二次出现的下标排序
只需要用 map < int, int > 来记录出现的次数
然后就过了
D
题意：
孔祥琸去了一家餐厅，他要吃 $ n $ 份饭，每份饭可能是有毒的
他要是吃了有毒的饭，会肚子疼
如果他现在肚子疼，而且又吃了一份有毒的饭，那么世界上的祸害就少了一个，否则他的肚子立刻就会好起来
每份饭有美味度 $ y $，和是否有毒的标识 $ x $，求他不死的前提下能品尝的最大美味度（他可以选择不吃哪份饭）
（题里 $ n $ 的范围是 $ 3 \times 10^5 $，他这么能吃吗？）
这个题我们需要写 dp
设 $ dp_{i, 0/1} $ 表示他吃到第 $ i $ 份饭，和他肚子的状态
然后考虑有毒的情况
他吃的话，肚子一定疼，所以他之前肚子是好的，也就是上一份饭是无毒的
不吃就是，上一盘把上一盘的状态延续
无毒的情况如下：
他如果吃，就不论之前的状态如何，直接更新
否则就可以考虑把之前的情况延续
然后就做完了
E
题意：$ n $ 个数，$ q $ 次操作，每次操作令 $ a_{x_i} = y_i $，每次操作完求前 $ k $ 大之和
这个题考虑平衡树，可以很方便的求出每个数的排名
我们考虑前 $ k $ 大的和用一个变量记录
我们先考虑插入，插入的时候我们需要查询排名，如果能排到前 $ k $ 大，就把原先的最小的顶替掉，同时处理答案
删除的时候，如果删掉了前 $ k $ 个，就把第 $ k + 1 $ 大的顶上
然后每次把 $ a_{x_i} $ 删掉，然后插入 $ y_i $
接着输出答案就可以了
F
题意：有 $ n $ 个长度为 $ m $ 的集合 $ s $，定义 $ f_{s_i, s_j} $ 表示把两个集合并起来中集合 $ i $ 中所有数排名的和（从小到大）
求所有 $ f_{s_i, s_j} $ 保证 $ i < j $
所有集合的数互不相同
考虑计算的东西是 $ \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} f(s_i, s_j) $
这里考虑枚举一个 $ k $，表示枚举 $ s_i $ 中的元素，然后他的排名如下：
在 $ s_i $ 里面的排名是 $ k $，在 $ s_j $ 里面的排名暂时记为 $ c_{j, a_{i, k}} $
然后我们要求的东西就变成了 $ \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \sum_{k = 1}^{m} (k + c_{j, a_{i, k}}) $
考虑把 $ k $ 提出来： $ \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \frac{m(m + 1)}{2} + \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \sum_{k = 1}^{m} c_{j, a_{i, k}} $
这里 $ \sum_{k = 1}^{m} k $ 也就是从 $ 1 $ 加到 $ m $，等于 $ \frac{m(m + 1)}{2} $
然后我们把前面的枚举完全拆开，得到 $ \frac{n(n - 1)}{2} \cdot \frac{m(m + 1)}{2} + \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \sum_{k = 1}^{m} c_{j, a_{i, k}} $
接下来考虑优化后面，我们可以把所有数离散化后插入到值域树状数组里面，然后一下子求得在所有集合里面的排名
具体操作是倒着枚举，一边计算一边插入，就可以实现不重复，可以自己想一想
然后就可以把 $ j $ 这一层循环给去掉：
$ \frac{n(n - 1)}{2} \cdot \frac{m(m + 1)}{2} + \sum_{i = 1}^{n} \sum_{k = 1}^{m} c_{j, a_{i, k}} $
复杂度是 $ O(nm\log{nm}) $