Day1
上午
信息学奥赛中的直觉与证明/jy
前面似乎非常亲民/se
nwerc2018 Equality Control
https://codeforces.com/gym/102483/problem/E
看起来好惊悚（
给两个程序，只包含列表常数，合并，随机打乱，排序。判断它们是否相同。
直接搞出最后的序列(每一段要么是一个常数，要么是一个序列随机打乱的结果)，然后尽可能合并，判断是否相同就行了。
nerc2019 Game Relics
在线性的情况下可以大胆使用期望的线性性。比如你要在\(n\)个东西里面抽一个，可以认为你抽了这些东西各\(\frac{1}{n}\)个。wa了再说嘛!
wf2016 Swap Space
有若干个硬盘，每个有一个空间上限和当前已经用了的空间，你需要买一个额外的硬盘，然后通过移动文件，让每个硬盘的空间都达到\(0\)至少一次。
看起来直接贪心就好了。让我们很难不想起一些奇怪的在图上走的贪心题。
先取门槛低并且有用的，因为不管门槛高低，都能让你的处境变好，应该尝试先少付出代价。
wc2020 Quests
你是一个无敌的游戏玩家，现在你在刷经验，每\(v\)个经验可以让你升一级。有若干个任务，每个说的是你在某个级别以上去做会得到某个经验值，在这个级别以下会让你的经验值翻\(c\)倍，所有的\(c\)是一样的。求做完之后最多得到多少经验。
肯定是先翻倍地做，那么考虑我们是
wfi2020 The Mind
ipsc2011 Flipping Coin
这个问题说的是，大家可以在游戏前
nerc2020 Is It Rated?
有若干个判断题，你的同学们回答之后，你得到了他们的答案并且回答，然后你会知道正确答案。找一个策略使得你错的比较少，具体一点是不超过错的最少的人错的题数的\(1.3\)倍再多\(100\)。
wf2020 Framing Pictures
旋转卡壳是在凸多边形边界上的旋转扫描线。
计算几何的扫描线真的是把连续变为离散。
nerc2020 Fiber Shape
每一条边是两个椭圆弧?然后直接算面积就行了。
nwerc2017 Connecting Dots
离奇题。
nerc2020 New Flat
这个是不是也很简单啊，答案要么是可以达到90度，要么就会受长度限制而卡住，此时平移之后肯定可以一端卡在一个端点上，另一端在边界上，于是旋转卡壳卡一波就行了。
诶是不是达到了90度也可以卡在顶点上（
nwerc2019 Kitesurfing
利用贪心缩减状态数。
nwerc2018 Date Pickup
要么是走一个环，要么是走一条足够长的路。
二分答案，求出哪些点是可以在上面磨叽的，然后如果有一个环就可以在上面一直走，否则就用拓扑排序求出最短路和最长路。呃好像只需要求最长路?
wf2015 Pipe Stream
判断是否有解和求次数几乎是一样难的。
考虑每个位置\(p\)有一个时间的分界点\(\frac{p}{v}\)。查询会导致时间流逝\(s\)时间，于是我们的二分不能太简单，于是需要构造或者计算决策树。
wf2017 Son of Pipe Stream
结论是，忽略
员交
讲道理这个员交看起来比较离奇（
hehezhou 双射法
?
yg 模拟费用流
终于又见到这个了（
枚举增广路，凸性，
agc018c Coins
收录于 AGC选胡。只需要枚举所有可能的增广路即可。
noi2019 序列
还是枚举所有可能的增广路即可。
这两个问题看起来就是可能的增广路可以归为几类，然后这被进一步总结为它们只可能是若干关键点之间的路径。
餐巾计划问题
你每天需要\(a_i\)个餐巾，用完了可以送到洗衣机，两个洗衣机分别需要洗\(d_1,d_2\)天，花费\(r_1,r_2\)的钱，也可以用\(p\)的钱买一个新的餐巾，求最小花费。
问题是怎么确定买了多少餐巾，然后剩下的都可以贪。
根据凸性，猜测三分正确。
考虑子图
如果图可以分成两个子图\(S,T\)分别包含\(s,t\)，并且只有一条边从\(S\)到\(T\)，那么关于这条边的流量，整个网络和两边中任意一侧的费用流也是凸的。
最常见的是图看起来像一条链加上一些东西的时候，用数据结构维护链。
zjk 邻项交换排序
在很多年以前，ouuan好像总结过这个，现在zjk写进集训队论文了。邻项交换说的是要构造一个cmp，然后验证它是不是严格弱序，如果它是那就赢麻了，否则输麻了。
zjk的贡献是指出了树上的奇怪贪心中，合并到父亲的贪心做法和这个东西的强相关性。
Day2
下午
数据结构题/jy
ioi2021 位移寄存器
这也算数据结构题/jy
是不是已经讲烂了（
再考虑一遍?
看起来我们难以直接比较，于是考虑实现一个比较器之类的东西来做排序网络。
然后容易想到把两个数相减判断符号位之类的。这个看起来确实是可行的，我们可以用一个掩码把符号位拿出来。
现在已经会做求\(\min\)的subtask了，也就是直接分治一下合并起来。具体一点，分成两半，让左半边和右半边对着比较，然后把剩下的用刚才那个掩码搞出来这样的。这个操作次数是\(O(\log n)\)。
然后我们考虑排序。使用最简单的排序网络，也就是奇偶移项排序即可。用一个掩码把奇位和偶位分别拿出来，比一下，根据轮数看哪边往前走就行了。感觉很对。这个操作次数是\(O(n)\)。
讲道理可以奇偶归并做到\(O(\log^2 n)\)，并且好像也有人写了，但是实在是没有必要（
ioi2021 地牢游戏
这个实在是不愿再写了（
uoj671 诡异操作
感觉好像在noi前看过这个题（
值域非常大，于是直接吉老师就死了。
考虑能不能把那个\(n\log n\log v\)上的\(\log n\)砍了之类的。呃原做法应该是每个点维护和和所有数的or，如果or会被and改变，或者div的时候or不为0，就递归下去。
能不能不要线段树?好像很困难。
考虑我们同时维护每一位有多少个数出现了，然后处理or的时候就可以直接统计变化了。具体一点?
我们or的时候打一个标记，表示区间内哪些位被清空了。div只会在每个点增加不超过\(\log v\)位，然后现在好像是or的复杂度下降了而div的复杂度上升了（
考虑能否给这个东西加加速。注意到每个点存了128个不超过区间长度的数，我们用一个离奇trick反过来压位，存区间长度个不超过128的数。
uoj592 新年的聚会
看起来比较离奇。
如果\(n\)足够大，我们把图划分成\(O(\sqrt{m})\)个独立集。
qy表示可以考虑二分图，并且已知两边的点集怎么做，此时可以考虑类似于四分树的做法，同时在两边进行划分。然后这个查的点数看起来是\(O(m\log n)\)。
现在假设我们已经划分成了\(O(\sqrt{m})\)个独立集，我们对所有这些独立集两两做这个操作，然后就无敌了。
uoj604 赶路
看起来是简单题。我们把这个线段拿出来，然后考虑绕着这个线段把点加上去，然后我们不知道怎么绕着线段，但是我们会绕着点。
然后你发现我们就赢麻了，从起点排个极角序，然后它就赢麻了。
但是你发现可能会出问题，也就是有可能会有一步绕的超过了180度。发生这个情况当且仅当起点在凸包上。如果终点不在凸包上那就换过来啥事没有，否则两个点都在凸包上的话，可以直接尝试剥凸包。
另一个简单做法是直接分治。
主要问题是这题spj怎么写，这个题当时因为spj不彳亍而只出了\(n^2\)。
partation tree rush/jy
cf1280 H. Red Blue Tree
看起来很复杂。考虑能不能树剖之后搞个限制复合之类的东西。
结点颜色的变化量在修改之间可以非常大。
注意到这是儿子，所以改颜色的变化上传到了第一个不再变化的地方就再也不会变化了。这个可以在树剖上二分限制复合，然后做一个推平。
剩下的问题是改\(k\)怎么做。考虑我们不要维护颜色，而是维护对\(k\)的限制(也就是\(k\)多么小这个点才是蓝的)，做完了。
呃具体一点，我们每个点维护重儿子分别是蓝色和红色的时候，使它是蓝色的最小的\(k\)，然后转移就是轻儿子里面一个什么东西的\(\min\)，我们预处理这个，直接做可以数据结构维护轻儿子，反正肯定能做（
cf566 C. Logistical Questions
看起来有个牛逼做法，基于点分治的静态top tree上二分，每次走到更优的子树即可。
我也不知道正确性是个啥（
cf1083 C. Max Mex
值域线段树维护每个区间构成的链，问题是怎么合并两条链。
链并在什么时候不是一条链?
cometoj cojc8 F. 黄金体验 弱化版
树，正的边权，一开始只有根，支持挂一个叶子，查询选\(k\)个点构成的斯坦呐树边权最大值。
结论是从直径端点出发长链剖分之后取这个直径端点和前\(k-1\)长链的端点。
然后用lct同时维护直径和长剖就彳亍了。
未知来源题
完全二叉树(每个点要么是叶子，要么有两个儿子)，每个点有一个点权，是左右儿子的点权差的绝对值加上这个点的一个某种权值\(v_i\)。支持修改一个点的\(v\)，求根的权值。\(n\leq 2\times 10^5,v_i\leq 20\)。
比较离奇。爆力维护每个点进行每一种操作之后会变成什么。
joisc2019 day3 Bitaro穿越时空
不懂，反正我觉得直接ddp就彳亍了。
gym102979 K. Knowledge Is…
\(n\)个点，每个点有一个区间作为权值，两个点连边当且仅当区间不交，求最大匹配。
这个图是二分图吗?好像不是。于是我们不懂了。
将来可能会补（
gym102586 L. Yosupo’s Algorithm
平面上有红蓝两种颜色的点，每个点有一个权值，每次给一个横轴的区间，选一个红点一个蓝点，至少有一个在区间内，使得红点的纵坐标比蓝点小，两个点的权值和最大值。\(n,q\leq 10^5\)。
这个偏序对看起来还是挺困难的。
考虑找个性质筛一筛，然后考虑了什么筛成单调的，然后这个就没啥用。
考虑牛逼想法，我们直接分治，然后这会得到\(n\log n\)对点，就赢麻了。
TB5(模板 势能均摊莫队)
为什么会讲这个（
讲道理前两天我还想用什么按势能分块的方法切离奇题，但是这玩意真的很离奇（
按势能分块往往只能用于限制指针移动时均摊数据结构插入和撤销的复杂度，所以看起来跟回滚莫队结合的尤其好。
qy说他用多叉树启发式合并才卡过去了（
员交
huhao 忘了题目（
可能是杂题选讲?
未知来源题
未知有根树，你每次可以查询一个点集，交互器给出它们子树并中的点两两距离和。求出这棵树。
考虑查询\(S\)和\(S+u\)，可以知道\(S\)中是否有\(u\)的祖先，借此二分\(u\)的父亲即可。
集训队互测____ 整数
有一个排列，你每次可以问一个位置\(i\)，交互器有一个数\(x\)，它会把\(x\)加上\(2^{p_i}\)然后返回二进制\(1\)的个数，一开始你并不知道\(x\)，操作不独立。在\(O(n\log n)\)次查询内求出这个排列。
考虑我们连续两次问\(i\)，那么我们可以知道这个数第\(p_i\)位的值，并且给它的第\(p_i+1\)位加上\(1\)。
Empty the Bucket
Hat Problems 1
这个看起来很经典（
dengyaotriangle
区间lis/jy
单位蒙日阵/jy
我记得去年apio的时候讲过，蒙日阵说的是满足四边形不等式的矩阵。如果一个蒙日阵满足\(a_{i,0}=a_{n,i}=0\)，元素都是自然数，并且相邻元素差不超过\(1\)，那么它就是简单亚单位蒙日阵。
简单蒙日阵指的是\(a_{i,0}=a_{n,i}=0\)，这个性质保证了一类二维差分在它上面可逆，这种差分，是进行\(O(n\operatorname{poly}(\log n))\)快速简单单位/亚单位蒙日阵乘法的基础。
注意到\(a_{l,r}\)表示\([l,r]\)的lis长度，那么它是简单亚单位蒙日阵。
蒙日阵在(min,+)矩乘的意义下是封闭的，也就是说它们这么乘得到的还是蒙日阵。
Day3
上午
dmy的照片好离谱（
杂题选讲。
stars
有一个\(k\)维空间中的点的序列，对于每个区间，使得存在一个点(这个点不一定在序列中)，满足区间内每个点和它都有至少一维坐标相同，求这些区间的长度和。\(n\leq 10^5,k\leq 5\)。
考虑怎么判定一个区间是否可行。考虑我们从每个点向\(k\)个方向画直线，如果一个点上被所有点的直线穿过，那么选它就行了。
但是这样做会有一些边界情况，比如这个点也在区间中存在，那么容易把它算成两次，不过给这个单点\(-(k-1)\)似乎就彳亍了。但是这样各维度就不独立了，这就很难受。
考虑\(k\)很小，于是我们考虑一个牛逼做法。考虑第一个点哪一维被搞定了，我们枚举这个维度，然后把和它相同的全都扔了，再看下一个。但是我们没法支持快速 看下一个 这样的操作，所以它就飞了。
另一个想法是，考虑我们不要双指针了，从每个位置开始往后记搜。我们的状态只需要现在扔了哪些点
pa2021 r1 A
长\(n\)的序列，每个数在\(1,...,m\)之内。每次可以扔掉一个区间，要求这个区间的开头和结尾相同，扔掉之后左右合并起来，求有多少种序列可以被扔空，膜\(10^9+7\)。\(n\leq 3000,m\leq 10^9\)。
考虑如何判定一个序列是否可行，容易发现这当且仅当它可以分成若干个左右端点同色的区间，这些区间不交并且并起来是整个序列。
然后我们就强行dp一下就好了。但是这个会出问题，因为一个序列可能会被算两次，比如112122可以删1121和22，也可以删11和2122。
考虑怎么修补一下让它只算一次。我们看一看判定的强行dp是什么，说的是\(dp(i)\)表示前\(i\)个能不能删空，然后我们直接考虑什么时候\(dp(n)\)是true，你发现它和前面任何一个true颜色相同的时候就彳亍，于是我们记录有多少个这样的颜色，就可以只算一次了，离奇的事情是这玩意也可以转移。
Guess
Alice和Bob玩猜数。Alice每次要告诉Bob他猜的数是不是\(\leq\)Alice所想的数，然后她可以骗一手，但是也只能骗一手。求Bob第一轮分别猜了\(1,...,n\)，并且Alice回答了是，接下来Bob最坏情况下需要多少轮才能猜中。
考虑我们转化一下，Bob每次给出一个\(x\)，Alice选择把所有\(\leq x\)或者\(>x\)的数覆盖一次，如果一个数被覆盖了两次那么它就不可能是答案了。Bob希望尽快使得只有一个数被覆盖\(\leq 1\)次，而Alice相反。这俩是完全等价的/jy，另外好像所有的猜数都可以这么转化。
然后你发现去掉所有\(\geq 2\)之后，只可能有一个前缀和一个后缀是\(1\)，于是就可以设\(dp(i,j,k)\)表示长为\(i\)，\(\leq j,\geq k\)的都是1，而别的都是\(0\)这样的，复杂度是\(O(n^4)\)。
然后考虑怎么优化，这玩意看起来很有决策单调性，于是变成\(O(n^3)\)。
此时状态数也是紧的了，我们需要缩减状态数。注意到答案不超过\(2\lg n\)，于是维度交换即可。
维度交换下决策单调性啥的是不变的，但是我们需要考虑如何精细实现一下。另外可以考虑到有些决策单调性是维度交换之后才能看出来的?
pa2021 r2 A
树，可能是负的边权，找到若干个边不交的长\(4\)的路径，使得权值之和最大。\(n\leq 5\times 10^5,\vert w\vert\leq 10^9\)。
考虑直接做怎么做，我们状压下面的四层，然后就死了（
考虑不要这么爆力，设\(dp(u,0/1/2/3)\)表示已经有经过\(u\)的一条还未完结的长\(0/1/2/3\)的链(并等着继续往父亲延伸)的最大权值和，转移需要给每个子树选一个向上延伸的长度，使得\(0,2\)拼起来，\(1,1\)拼起来，\(3\)可以直接连过来。
然后我们在儿子之间用一个dp来计算，只需要记录\(0,2\)的个数差和\(1\)个数的奇偶性。
这个复杂度非常有趣，如果进行random_shuffle，那么任何一个固定方案中\(0,2\)个数差的绝对值最大期望是\(O(\sqrt{n})\)(但是所有方案的最大值可能会超过这个，不过反正我们只需要看最优方案)。这个结论基于随机游走，也就是\(0,2\)个数和是\(n\)，于是random_shuffle之后最大差是\(\sqrt{n}\)级别这样的。
可以多shuffle几次。
Snackdown 2021 final Bakery
店里有\(m\)个员工，接下来\(n\)个整时刻都有\(p\)的概率会来一个顾客，如果有顾客等着并且有空闲员工，那么员工就会过去服务，而服务一个顾客需要\(d\)秒。求所有顾客等待时间总和的期望，输出实数。\(n\leq 5\times 10^4,m\leq 10,d\leq 10^3,0.4\leq p\leq 0.6\)。
在某个时刻员工的状态只有是否在服务，但是在时间维度上看每个顾客还有一个距离服务结束的时间。
考虑一个牛逼想法，我们钦点第\(i\)个员工服务所有到店时间膜\(m\)余\(i\)的顾客，也就是说如果现在是\(t\)，有个员工空出来了，那么他必然可以是第\(t\bmod{m}\)个。
然后就每个员工分开dp就彳亍了。
Snackdown 2021 final Robbery 加强版
背包，每种物品有无限个，你可以选择\(k\)个物品，恰好把背包填满，并且价值之和尽可能大。\(n\leq 1000,k\leq 10^9,1\leq v\leq 10^9\)。
注意到要刚好填满，这就非常离奇。
考虑用一下那个牛逼倍增(max,+)卷积做法，然后就\(O(n^2\log k)\)了（然而这可能居然是出处之一
agc044e
圆上有\(n\)个点，你一开始在其中随机一个点出发，然后如果你在\(i\)，你可以选择结束游戏并得到\(a_i\)的钱，或者花\(b_i\)的钱随机往左右移动。假设一开始你有足够多的钱，求最优策略的期望收益。输出实数。\(n\leq 2\times 10^5,a_i\leq 10^{12},b_i\leq 100\)。
首先不管你拿着多少钱，在每个点的决策是一样的。也就是说在一些点你会选择走，另一些点选择溜。
考虑这些溜的点把环划分成若干段，每一段会一直游走到段的两端就停下。但是我们完全不知道这个是不是能够成功。
考虑直接做，我们一开始初始化为每个点都直接开溜，然后进行若干轮，每一轮每个点看走到旁边的点是否更优。然后我们猜测一直迭代就彳亍了。也可以把这个改成类似于spfa的东西。
你发现稳定当且仅当所有位置都是\(dp(i)=\max(a_i,\frac{dp(i-1)+dp(i+1)}{2}-b_i)\)，然后感觉这个很眼熟，发现如果\(b_i=0\)那就是每个点贴到\(a\)的上凸壳上，于是可以考虑一个离奇想法，我们把\(b_i\)消掉，也就是把\(a_i\)换成一个\(c_i\)，只需要设一个\(c_1\)然后转一圈解出来就行了。
agc056e
圆上有\(n\)个老鼠，于是分成了\(n\)段弧，每一段有一个长度\(a_i\)。你会扔\(n-1\)块奶酪，每次按弧的长度加权随机一个弧，然后奶酪会顺时针移动，遇到一只没吃过奶酪的老鼠就会被它吃掉。最后会有一只老鼠没吃奶酪，求每只老鼠成为不幸老鼠的概率，膜\(998244353\)。\(n\leq 40,\sum a_i=100\)。
\(40\)体现了离奇性。
考虑我们一次扔一块和一次扔所有的看起来是一样的。
一只老鼠没有吃到，那么这个看起来就像一个括号匹配。然后我们就拆开了直接做即可。
好像难度在于看出一次扔一块和一次扔所有看起来是一样的。
构造题图一乐/jy
icpc nanjing site的某个题
圆上有\(n\)个灯，每次你可以选一个灭的灯，把它和它相邻的灯的状态反转，在\(2n\)步之内点亮所有灯或者报告无解。\(3\leq n\leq 10^5\)。
显然可以高消消出每个灯是不是应该点，于是问题是怎么才能在一个灯灭了的时候去点它。
考虑如果所有灯都亮着，那就没救了。如果有灯灭着，我们找到灭着的灯的连续段的两端，找一个尝试点一炮，然后它的一侧亮着的灯就灭了，然后就可以继续点下去，直到把整个段都点成灭的一次，然后我们再从那边开始再点过去一遍，感觉上就可以搞定了。
然后dmy讲了一个牛逼做法。考虑如果一个灯是灭的，并且它需要点，那么我们就直接点它。点完之后，每个灯要么是亮的并且不需要点，要么是亮的并且需要点，要么是灭的并且不需要点。对于第一种不用管了，第二种的话，它旁边过一会一定会有一个灭的并且不需要点的，不然点它就没有意义了，第三种类似。不断找到这样的位置去点就行了。
t宝的某个题
所以t宝是谁（
有\(n\)个灯，它们会按照排列\(p\)的顺序点亮。给每盏灯染\(1,...,23\)的颜色之一，使得在任意时刻讲所有点亮的灯排成一排，任意非空子段中都存在一种颜色出现恰好一次。\(n=12100,k=23\)。
相当于有一个序列，然后每次往里插入一个。
考虑23是个啥，感觉不知道（
考虑强行构造，我们考虑每次插入之后变化了的区间，新插入的颜色要么和原来这些区间中的颜色都不同，要么恰好没有毙掉这些区间中的某个恰好出现一次的颜色。
然后就可以想到二维数点那一套的东西，这个颜色能贡献的是一个2-side的区域，并且随着插入这个区域会缩小，我们需要让所有区域的并是整个平面。
容易想到要用一个分治，但是这个序列是在任意位置插入，所以我们就输麻了。
题解非常牛逼。考虑我们找到出现次数最多的那种颜色，然后我们要让这个颜色满足任意时刻不能有两个相邻的，此时把它删掉之后剩下的合法就行了。然后为了做到这个，我们可以直接把相邻过的连边，然后胡乱贪心贪一个独立集，可以证明如果按照加入的倒序贪心，至少可以选出\(\frac{1}{3}\)的点，于是最后就可以搞定了。
Anton的某个题
好像可以在codechef找到。
有一个排列，每次可以选择一个区间，交换其中最大值和最小值，把这个排列排序。\(n\leq 3\times 10^4\)，你有\(3\times 10^6\)次操作。
首先可以把它变成，选一个区间，端点分别是最大值和最小值，然后交换端点。
考虑归并。
左右分别排序之后形成了两个单调序列，然后我们强行构造即可。
下午
构造题/jy
图一乐/jy
Parks
平面上有\(n\)个点，两维坐标都是偶数，保证如果对于每一对距离是\(2\)的点连一条边，整个图是连通的。构造一个生成树和一个\(n-1\)个点的序列，这些点两维坐标都是奇数，使得存在这些点到生成树边的双射\(\varphi\)，满足\(p\)和\(\varphi(p)\)的两端点构成等腰直角三角形。\(n\leq 2\times 10^5\)。
考虑显然我们几乎应该让生成树边长是\(2\)或者\(2\sqrt{2}\)这样的。
考虑一条斜的折线，每一段长度是\(2\)，它会经过若干个两维坐标都是偶数的点。然后如果一些点在这上面，我们可以给出离奇的构造。
待补/fn
挑战哈密顿2
平面上有\(n\times m\)个点的网格图，两个点的距离是\(1\)或\(\sqrt{2}\)就连一条线段，要找到一条哈密顿回路，满足任意连续两条线段不平行，并且任意两条线段不在端点之外相交。\(nm\leq 10^6\)。
考虑从外圈往里缩。比如我们可以往右上走一步，然后往左走一步，这就非常牛逼。走一圈回来之后，精细处理一下，我们就递归到了里面的情况。足够小的情况要么是平凡的，要么可以搜出来。但是过小的情况是无解的，最后看起来要搜\(7\)以内和\((9,9)\)的情况。
Pattern Lock 魔改版
平面上有\(n\times m\)个点的网格图，任意两个点都有一条线段。你要找一个哈密顿回路，使得经过每个点的两条边构成一个锐角，并且一条边不能穿过任何点(也就是说它上面只能有它的端点)。\(nm\leq 10^6\)。
考虑还是从外往里搞，我们可以拐着转一圈，里面搜一搜，然后居然真的就做完了。比较离奇的事情是yhx给出的构造需要从外圈的上面接到内圈的下面。
开关
有一排\(n\)个灯，每次可以选择一个区间，其中亮的和灭的个数相同，把每个灯的状态反转。把\(s\)操作成\(t\)。\(n\leq 10^5\)，你可以用\(6666666\geq 6\times 10^6\)次操作。
考虑操作可逆，于是可以都排一下序，然后搞回去。
考虑如何将\(1111111100000000\)这样的变成\(000000000001111111111\)这样的，也就是把01位置互换。
直接翻就行了，这个过程类似gcd。
然后对于一般的情况，直接分治即可。
给一个排列
生成仙人掌
\(n\)个点，\(i,j\)之间边权是\(\vert i-j\vert\)，求最大生成仙人掌。\(n\leq 10^5\)。
考虑不超过长度\(\geq 5\)的环，因为它可以拆成两个三元环。
考虑几乎所有的边都会贴着\(1,n\)。
最后答案是\(\lfloor\frac{8(n-1)^2+4}{9}\rfloor\)，看起来非常离谱啊/jy
cf329e
平面上有\(n\)个互不相同的点，求曼哈顿距离意义下的最长哈密顿回路。\(n\leq 10^5\)。
这居然不是npc（
考虑一个离谱性质，在一维的情况下构造是显然的，而在二维的情况下，如果按照一维的构造则可以取到一维问题的最大值，否则几乎会取到一维问题的次大值。于是我们尝试\(O(1)\)种情况即可。
ccpc final 2018 C. GCD Land
感觉上好像省集的时候收录过（
joisc2017 day4 B. City
离奇题。已经收录于 刷穿joi。
Day4
上午
看起来好恐怖（
感觉ioi题还是等到114514年后再做。
下午
咋提/jy
dcx声音听起来好帅啊/se
ioi2021 d1t1 分糖果
让人想起 饮食区。
先离线，扫描线扫序列，线段树维护时间。
考虑如果中间没有碰过上界或者下界，那就无敌了。否则考虑找到最后一次碰到的位置，还是无敌了。
问题是用线段树维护最后一次碰到的位置。维护前缀和的min/max，然后你发现如果直接维护这个前缀和的话，它看起来会被上下界限制住，于是我们维护的是不对的，求出来的碰上下界的时间也是不对的。
考虑一个离奇想法，我们发现如果一个区间内前缀和的极差超过了上界，那么在这个区间必然碰过界，并且如果区间端点分别是min/max，后面的那一个是min还是max说明了碰的是上界还是下界。
线段树二分找到左端点最靠后的这样的区间，在此基础上再找到最靠后的右端点，于是在右端点再后面的时刻只可能碰到上界或者只可能碰到下界，而两种情况我们刚才分开了。
考虑这个怎么做，你发现此时刚才我们想的那个东西变对了，比如这个右端点是一个min，那么我们已经碰过了最离谱的下界，接下来只可能碰到上界了。那么考虑怎么求出啥时候碰上界，
ioi2021 d1t2 钥匙
这个让人想起 病毒实验。可能叫这个?
别乳卡就彳亍了。
cerc2013 G History Course
Day5
boomed/cy
看了一眼A，推了推有什么结论，发现啥也不会/cy
B写了4.5h回滚莫队+链表，然后卡到了随机数据本机5.1s(我是amd r9-5900hs)，看起来并没有什么希望/cy
C写了0.5h，纯随机也没调出来，获得了0pts/cy
看起来B可以莫队+压位线段树冲，也就是64位压成一块，用线段树维护各块，这就得到了一半的常数，并且实际上减少cache miss的效果可能更显著。这个为什么没想到呢/fn
然后这也是我第一次写回滚莫队，居然写出来了（
A. 这个看起来就很像在转。画出来感觉上它不是在转，但是又像是在转。
把括号序列画成左儿子右兄弟的树，然后它就真的在转了。然后它看起来并不是所有转的方式。
然后先标准化成几乎是一条右链的形态，再把每个点转到正确的位置，胡乱讨论即可。看起来好离奇?
好像有个核心部分是要找一个不幸点把它扔过去辅助旋转。
B. 考虑每个数，如果它的前驱在它左边它就会贡献\(1\)，否则贡献\(-1\)，如果后继在它左边它也会贡献\(1\)，否则贡献\(-1\)。
考虑一个牛逼想法，我们在序列上分治，然后两边之间的贡献，必然是左边\(-1\)右边\(1\)。
考虑先扫左边，每次加入一个右边的元素，如果它插在了左边的两个位置之间，那么答案的变化量对这两个位置是独立的。于是我们只关心每个位置有没有插入，而不关心插入的具体是什么了。然后我就不懂了（
一个牛逼根号做法是对值域进行分块，把每一块单独拿出来，把位置离散化，在上面爆力枚举所有可能的查询然后用差分-前缀和搞回去，而块间的贡献只有根号次。
C. zyb : 首先给大家看一下这个出题人，他std的长度/jy
20k/jy
看起来非常离谱。考虑搜个决策树，然后失败了。
每走一步用A*搜一下，随便剪剪枝。
出题人给出一个离奇结论，决策树搜的好的话，除了r和s开头的都必然可以猜出来。不过这谁看的出来呢（
zyb做法是，直接爆力枚举下一步的决策，找分支最多的。
wzm看起来是枚举下一步的决策，找期望得分最高的。