A 贪心
牛逼贪心，真的神秘。
在和牛逼学弟$B.White$讨论后，产生了以下思路：
若$a_{1}…a_{x}$是一个$1$到$x$的排列，我们称$a$是饱和的。
考虑$p$的任意饱和前缀$p_1…p_{i}$，若这$i$个数能被划分为两个上升序列，则这一段无论如何划分，和$p_{i+1}…p_n$都是互不影响的。
证明：$p_{i+1}…p_{n}$中的任意元素都比$p_1…p_i$大，所以后面划分的两个序列可以随意拼接到前面两个序列后面。
由上得，所有饱和前缀与其剩余部分的结果相互独立，我们可以处理出所有饱和前缀，然后用这些前缀的位置把$p$划分为多个独立的饱和段，所有饱和段互不影响。
此时，我们只需要求出所有饱和段的划分结果，然后所有饱和段的最大值减去最小值之和就是最终的答案。
考虑如何求出某一个饱和段的答案，我们有以下结论：
- 对于一个饱和段，其不含有任何饱和前缀
- 对于一个饱和段，其最终形成的两个序列唯一
- 从头开始，每次找到比当前大的数直到没有，此时形成的序列一定是两个序列之一（或者无合法序列）
证明：
假设饱和段中存在一个饱和前缀，则其会产生两个新的饱和段，这和前提（找出所有$p$的饱和前缀划分为多个饱和段）矛盾，因此1得证。
考虑一个饱和段中，元素$a$后面第一个比他大的数为$b$，则有三种情况：
- $b$不存在，此时$a$后面所有元素一定不和$a$属于一个序列
- $a,b$相邻/不相邻，此时在一个序列中$a$后面一定紧接$b$
- 证明：由(1)知饱和段中没有饱和前缀，则存在其他比$a$小且在$b$之后的数$c$会放在和$a$相异的另一个上升序列中，由于$c<a<b$，我们只能将$b$放在$a$后面
当序列中每一个数作为$a$时，根据以上规则，我们都会将$b$后面第一个大于$a$的数放在$a$后面，因此序列的位置关系是确定的，(2),(3)得证。
由(3)知，我们可以遍历一遍获得一个上升序列，然后把剩下的放到另一个序列里，若剩下的数无序则无解。
总复杂度$O(n)$。
感觉把std踩了，这个线性做法是目前CF上跑的最快的
B 签到
当$n$为奇数时，这$n$个数模$k$同余；当$n$为偶数时，按照位置奇偶性构成两个模$k$同余的等价类或。
需要特判$(4,3 )$，因为此时模$k$的结果为$0,1,2,0$，$(1+3)\%3=0$，但是只有$(4,3)$这一种情况是特殊的（证明思路可以考虑$0$必须在图中出现$\frac{n}{2}$次）
C 图论
涉及中位数最值问题可以考虑二分答案，此时图中所有点权变为$1$或$-1$，问题转化成判断是否存在一条$1$到$n$的点权为正的路径。关于SPFA，它死了
考虑点权的特殊性，可以推出以下结论，下面$(a,b)$表示一条连接两点权值分别为$a,b$的边：
- 如果存在一条$(1,1)$边，一定可行（在这条边上来回走）
- 如果存在一条$(-1,-1)$边，我们不会去走（因为走$(-1,-1)$需要用$(1,1)$来补正）
- 如果我们只走$(1,-1)$和$(-1,1)$边，当且仅当$c_1=c_n=1$时可行。
DFS/BFS/DSU判断即可。复杂度$O((n+m)\log10^9)$
D 签到
E 几何
推$O(1)$公式 (x)
无脑$O(\log\frac{1}{eps})$二分 (√)
直接二分半径，然后判断和边界是否有交点（点到线段距离），注意判断线段叉乘时精度要在$10^{-9}$以上。
计算几何嘛 WA了改改精度多交几发
Part 2: $O(1)$公式的推导
todo
F 签到
G 字符串
还没补，目前进度MLE84/TLE64
H 图论
读题面中所给代码，得知其作用是标记所有和$v$联通且$\Delta=a-b=a_{v}-b_{v}$的点，然后把这些点的$\Delta$都置零。
如果暴力进行1和3操作，发现对点的访问次数均摊后是线性的（一次1操作改变一个点，一次3操作把修改过的点还原），复杂度瓶颈在于1和3操作过程中需要遍历所有邻接边，因此考虑优化这个过程使得我们不需要遍历边而获得所有权值相等的连通点集。
我们可以用set来记录一个$(a_x-b_x,x)$的pair，每次从某个点开始dfs的时候就直接在set上二分，这样3操作的复杂度就合理了。
但是此时1操作修改树上节点时，还需要遍历并更新所有邻接点的set，瓶颈依旧在。如果只考虑以上做法，可以发现对于图也是一样的，此时并没有利用到树的性质。
假设我们定$1$为根，set里只记录子节点，此时对于1操作，我们只需要修改其父亲的set，因为子节点要访问父亲的时候直接寻找$a_{father}$就够了。而对于3操作，我们直接往根走直到$\Delta$不相等，然后dfs子树的set。
I 线段树
先把所有数放到$[0,10^6]$的桶里，设其为$b$，则一个非零$MEX$值$x$可以取的时候必有$b[x]=x$，所以考虑用线段树维护$b_i-i$的区间最值。当加入一个数$a$的时候对应$[a:10^6]+1$，减去的时候对应$[a:10^6]-1$。对于查询就直接在线段树上递归查询最右侧的合法位置，总复杂度$O(q\log10^6)$。
J 构造
一个显然的结论是，所有行和列的$MEX$都有且只有一个数不为$0$，且至少有一个为$1$。
所以可以先找出$0$的位置，然后对这一行和列填充小于$MEX$的数，空余位置可以用最大的数补全。其他行列就随便填了。
K 并查集
每次操作翻转两块，说明$1$和$0$的差奇偶性不变。如果我们将每次操作的两个位置连一条边，会发现每次操作会减少连通块中两个$1$或不变，因此只要带权并查集统计一下所有连通块内$1$的个数是否是偶数即可。
L dp
问题等价于求有多少种从底部走到某个端点的路径。考虑$f_{i,j}$表示从$(1,1)$到$(i,j)$的路径数，则有
有效状态最多$n$个，用map记录然后转移即可。