H Hard Calculation

LYF签到

J Mr. Main and Windmills

LYF简单计算几何

L Simone and Graph Coloring

题意：给一个排列，将其中所有逆序对中的两个点连边，要求连着边的点颜色不同，问至少要多少种颜色，输出方案。

解：按值从大到小处理，因为如果从最大点开始递增编号，某个点不会受到比它小的点的影响。一旦该点确定了答案，则将该点之后的区间与该答案取max。每次确定答案时查询之前对当前位置造成影响的最大值即可。

1e6组数据，要每次清空，用了memset
要输出1e6的方案，用了cout

T了好多好多发大概已经四五年没有这么T过了

另外的做法：答案大小等于最长下降子序列。方案贪心选择即可。

M Stone Games

题意：强制在线。给定一个长度1e6的1e9以内数列，询问1e5次，每次询问区间内数的所有子集的和的mex。

解：首先考虑如果有一段静态的数要求答案。经过思考可以得出一个比较显然的做法：排序后从前向后扫，若当前的前缀和+1比后一个数小，那么前缀和+1不能表示，否则继续进行该判断。

但是这个不能显然地用数据结构维护，因为没法维护区间内排序好的数列，而且每次扫的时候是线性的。那么考虑在值域上开线段树，区间查询则利用可持久化实现。可以发现，每次统计前缀和时，若发现该前缀和+1可以表示，则下一个前缀和必定大于当前前缀和的两倍，所以只需要log次查询即可。而每次查询显然也是log的。考虑到询问次数为1e5,两个log可以过。

小错误

写前缀和查询函数时，同样功能的两个函数(传入参数稍有不同)居然一个加了当前区间应全加的判断而另一个没加，导致T
以为该加longlong的地方都加了，结果函数返回值没改成longlong
调试时没有看清楚强制在线的方式，以为自己错了，对着正确的地方调了半天

补K Parallel Sort

题意：给定一个排列，每一轮可以挑选一堆位置对，使那些位置对上的数相互交换，但要保证位置对中的数互不重复。问至少几轮，输出方案

解：首先显然可以找出环来，然后可以发现每个环最多只需要两次就能解决。考虑对于开始的那张图，交换两个数将会造成的影响。显然这两个位置的入边是不受影响的，交换两个数相当于交换出边。如果每次交换相邻的边，将会每次将环缩小一半，会得到一个看似很优秀的log次做法。比赛时王鼎写这个分治写得无比正确，我写的gen和spj在100000也完全检测不出错误。所以估计是有比log次更优的做法。

可以发现，如果采取相邻两两交换方法的反面——另一个极端——对称交换，那么拆一次就可以把任意大小的环拆成若干个大小为1和2的环。然后这道题就做完了。比如234561就换成165432然后就可以一步到位123456。

补G Gift

题意：很长

解：两个DP拼起来，注意一下特殊情况大概就行了？但是我看出是DP也没设计出状态

LYF