前言
这次挑战赛更难了亿点啊。为了精简题解长度，已经去了头文件、部分宏定义和快读快写。
T1
首先是 000 的情况：L1≤R2 or L2≤R1L_1\leq R_2\ \operatorname{or}\ L_2\leq R_1L1 ≤R2 or L2 ≤R1 ，两条线段不交/只交于一点。
然后暴力分讨。
1. L1≤L2 and R1≥R2L_1\leq L_2\ \operatorname{and}\ R_1\geq R_2L1 ≤L2 and R1 ≥R2
线段 L2R2L_2R_2L2 R2 被 L1R1L_1R_1L1 R1 包含。直接输出 L2R2L_2R_2L2 R2 的长度即可。
2. L1≤L2 and R1≤R2L_1\leq L_2\ \operatorname{and}\ R_1\leq R_2L1 ≤L2 and R1 ≤R2
线段 L1R1L_1R_1L1 R1 与 L2R2L_2R_2L2 R2 的交集为 R1L2R_1L_2R1 L2 。输出 R1L2R_1L_2R1 L2 的长度即可。
3. L1≥L2 and R1≤R2L_1\geq L_2\ \operatorname{and}\ R_1\leq R_2L1 ≥L2 and R1 ≤R2
类似于 1。
4. L1≥L2 and R1≥R2L_1\geq L_2\ \operatorname{and}\ R_1\geq R_2L1 ≥L2 and R1 ≥R2
类似于 2。
T2
依然是分讨。设 1≤i,j≤n,i≠j1\leq i,j\leq n,i\neq j1≤i,j≤n,i=j：
1. Ai,j=DA_{i,j}=\texttt{D}Ai,j =D：Aj,iA_{j,i}Aj,i 也应该为 D\texttt{D}D。
2. Ai,j=WA_{i,j}=\texttt{W}Ai,j =W：Aj,iA_{j,i}Aj,i 应该为 L\texttt{L}L。
3. Ai,j=LA_{i,j}=\texttt{L}Ai,j =L：Aj,iA_{j,i}Aj,i 应该为 W\texttt{W}W。
枚举判断即可。
T3
使用 map 计数字符串出现的次数即可。如果这个字符串没有出现过，就直接输出；否则要再输出出现的次数。然后在 map 对这个字符串计数。
T4
这题开始上难度了 qwq
首先看数据范围：M,N≤5000M,N\leq 5000M,N≤5000，也许我们可以设计一个时空 O(n2)O(n^2)O(n2) 的 DP。无后效性是满足的，第 iii 次硬币的状态由 i−1i-1i−1 次转移而来。
发现状态只需要硬币和计数器。所以考虑这样设状态：设 f(i,j)f(i,j)f(i,j) 表示第 iii 次掷硬币，计数器为 jjj 时的最大收益。从硬币维开始枚举。每一次枚举有两种可能：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
* 正面
设计数器本次显示 jjj，第 iii 次掷硬币时掷到正面可以获得 X(i)X(i)X(i) 元，计数器为 iii 时可以获得 Y(i)Y(i)Y(i) 元，则容易推得：
f(i,j)=f(i−1,j−1)+X(i)+Y(j)(j≥1)f(i,j)=f(i-1,j-1)+X(i)+Y(j)\qquad(j\geq1) f(i,j)=f(i−1,j−1)+X(i)+Y(j)(j≥1)
* 反面
计数器本次必然显示 000。可以由上一轮的所有状态取最大值直接转移而来，即 f(i,0)=maxj=0i−1f(i−1,j)f(i,0)=\max\limits_{j=0}^{i-1}f(i-1,j)f(i,0)=j=0maxi−1 f(i−1,j)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
结果为投掷第 nnn 次硬币的最大值，即 maxi=0nf(n,i)\max\limits_{i=0}^{n}f(n,i)i=0maxn f(n,i)。
实现还是很简单的。注意开 long long。嫌空间大可以把动态规划数组滚掉一维，是可选的。
T5
前置知识：位运算。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这道题直接模拟是 O(n2)O(n^2)O(n2) 的，必然超时。
首先位运算很多，发现位与位之间是没有关系的，我们考虑逐位计算，可以简单很多。接下来的讨论都是基于每一位的。
先考虑怎么降时间复杂度。发现每一次依次完成 1−i1-i1−i 操作后，一定是以下两个情况之一：
* 反转当位
* 将当位设置为固定值
然后考虑将 1−(i−1)1-(i-1)1−(i−1) 操作的情况拓展至 1−i1-i1−i。设有覆盖标记 t1t1t1，反转标记 t2t2t2。又分为六种情况：
* &0 操作。覆盖标记设 000，反转标记清零。
* &1 操作。无需操作。
* |0 操作。无需操作。
* |1 操作。覆盖标记设 111，反转标记清零。
* ^0 操作。无需操作。
* ^1 操作。反转反转标记。
如果存在覆盖标记，则直接将原数赋值为覆盖标记。如果存在反转标记，则对原数进行反转。每一次操作完毕后记录过程性答案，时间复杂度 O(n)O(n)O(n)。细节注释都放在代码里了。
T6
前置知识：归并排序求逆序对
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
首先忽略颜色限制。只能两两交换，把序列排成升序，需要几次操作？显然是逆序对的个数。使用归并排序可以在 O(nlogn)O(n\log n)O(nlogn) 的时间内求逆序对，这里直接贴上代码。
那么加上颜色限制之后，就变得复杂了。先不要急，首先求出原序列的逆序对个数。但是显然有一些逆序对不需要交换。是哪些逆序对呢？当然是同色的逆序对。因此，我们直接将各个颜色的数按序分进桶。（我就是因为没有按序被卡了好久www） 然后对各个桶内的球进行归并排序求逆序对。原序列的逆序对个数，减去同色逆序对个数，就是异序逆序对个数，也就是我们要求的答案了。
实现当然还是轻轻松松。注意一下 long long，然后桶使用 vector 维护就行了。总复杂度 O(nlogn)O(n\log n)O(nlogn)。
