$cyy$的五一第三天。。。。。
第一天搞了搞视频并写了一坨化学作业，第二天补了一坨题和一坨$tuosh$物理，第三天终于能开训练了
wangbadan队友@nocriz@yangdavid吃喝嫖赌欠下了三点五个亿，带着他们的小姨子跑了
只能自己训练。
当场会了ABCEG，过了BCEG，A是写了一坨发现$mle$，然后发现得改一坨东西才能卡进空间懒得写了
其实有些题场上根本就没看，补题的时候发现大部分题还是可想可做的，但是场上花在码上的时间太多了
再给我点时间J大概率也能想出来，这就六题了。。。。
要是我们三个人的话怎么着也能写七题吧。。。。
突然发现七题是咖啡鸡去年11月的水平。。有点小激动
感觉单人训练的话，果然题会做也写不完
这场难度略大，但也不是特别自闭
感觉效果不错
$task\ lists$：
$F$:想清楚
A.Rectangle Query
有$n\leq50000$个二维平面上的点（坐标值域$500000$）,依此给出$q\leq50000$个询问，每个询问给出一个矩形，表示这个矩形里的点有多少种不同的$x$坐标，多少种不同的$y$坐标
$solution$:首先把横纵坐标离散化，然后用$bitset$维护每行每列上点的情况，对行列分别建线段树表示一段连续的行/列上的点占据列/行坐标的情况，询问直接在线段树上做$bitset$或即可，相当于在线段树上求出一个$bitset$后，询问这个$bitset$的$l-r$位上有多少个$1$，行列一样的。
时间复杂度$O(n^2/w+qnlogn/w)$
空间$768M$，需要手写$longlong$压位，很麻烦，很恶心（白瞎了我写了$100+$行的自带$bitset$）
还有一个分块做法，将点按照$x/y$坐标每$\sqrt n$分成一块，预处理所有$i-j$块的$bitset$,询问时将多出的零散的$\sqrt n$个点和预处理好的点一起考虑即可
复杂度稍微优秀一些：$O((n^2+qn)/w+q\sqrt n)$
B.Game with a fairy
交互题
有$n=10000$棵智慧树，其中某些智慧树上有智慧果，你只知道$n$,不知道哪些智慧树上有智慧果，但保证至少有一棵树上有智慧果。你有$200$次机会，每次你可以猜一个智慧树的子集，如果这个子集只有一棵智慧树上有智慧果，那么你就赢了，你要保证在$200$次之内赢得游戏，只要你赢了交互器会告诉你的。
$solution$:从感性加理性出发猜了一种策略，然后大胆一发就过了。
策略如下：
随机$2^0,2^1,2^2$大小的子集各$15$个。
随机$2^3、2^4……2^{13}$大小的子集各$14$个
猜一次全集
这总共是$15·3+14·11+1=200$次
其实能猜出这个策略也不是瞎蒙的，也是有点依据的。以下是我当时的想法：
这个题不能通过失败的尝试获得任何信息，因此只取决于策略的构造
我们考虑大小为$1$的子集，如果我们随机$k$个都猜不中，那么有智慧果的智慧树的数量大概是小于$O(n/k)$个的
这样的话，我们大概就能知道智慧果不是很多，就可以大胆尝试增大子集大小
大概是增大成$2$吧。。。。。。如果所有随机的大小为$2$的子集都不行，那说明智慧果更少，要进一步增大。
大胆猜想可能倍增就可以
对于每个$2$的幂，我们取的次数平均一些是不是比较好。。。。。。反正不行再调参嘛
要记得最后必须猜一次全集，不然会出锅的
嗯。算了一下平均，那就这个策略了
过了。惊了
↑大概就是我场上的心路历程
如果哪位聚聚可以给出严格证明，感激不尽qwq
C.Portkeys
数轴上有$n\leq10^5$个传送装置$(x_i,l_i,r_i)$,当你处于$x_i$时，你可以用这个装置传送到$[x_i-r_i,x_i-l_i]\cup[x_i+l_i,x_i+r_i]$上的某个位置。有$m\leq10^5$个目标点，你一开始在$x_1$，问对于每个目标点，你至少需要经过多少个装置才能到达。
$solution$:将装置和目标点一起用$set$维护还没到达过的点，从$x_1$开始$bfs$，每$bfs$到一个就从集合里删去，复杂度$O((n+m)log(n+m))$
我甚至在场上傻乎乎地写了个线段树优化建图最短路，一开始没考虑坐标值重合的情况$WA$了一年，虽然很傻，好歹写了个线段树优化建图，锻炼了一下。
D.Maximal Common Subpair
给定两个长度小于$10^5$的字符串$s,t$，求他们的最长公共双子段。
定义：双子段：在一个字符串中，两个子段按照前后顺序拼接起来，称为一个双子段。
$solution$:把$s+t$建一个后缀自动机，每个节点表示一类子串，求出每类子串在$s$中出现最早的位置$x$，在$t$中最早出现的位置$y$，求这两个值使用线段树合并或启发式合并均可。取这类子串最长的长度$len$,这样得到$n$个三元组$(x_i,y_i,len_i)$,然后同样的，我们把$rev(t)+rev(s)$建一个后缀自动机，像上面统计每类子串在$s/t$中最后出现的位置和最长长度$len$,得到$n$个三元组$(u_i,v_i,leng_i)$
那么一个最长公共双子段便是：$max_{i,j,x_i<u_j,y_i<v_j}{len_i+leng_j}$
将所有三元组按照$x_i/u_i$离线，用树状数组维护关于$y_i$的前缀$len_i$最大值，按照顺序枚举$j$，在树状数组中查询更新答案即可
E.k-transpositions
初始数列是$1-n$的顺序排列，最多使用$k$次$swap$操作，问总共能得到多少种可能的排列。
数据范围：$1\leq n\leq10^9,1\leq k\leq 3000$
$solution$:我非常喜欢的一道组合数学题，场上过了，感觉还不错。
发现最多有$2k$个位置改变，我们对最终的排列进行环分解（即置换分解，差不多那个意思，就是把排列考虑成一堆环，我也不知道专用名词）。考虑大小大于$1$的$m$个环分别是$p_1,p_2……p_m$
注意到环之间不相关，并且可轻易证明，对于这样一个排列，我们至少需要$(\sum_{i=1}^mp_i)-m$次操作才能得到。
对于排列$A$,设$f(A)=(\sum_{i=1}^mp_i)-m$,即最少$swap$数
现在我们便可以枚举$f(A)<k$
考虑对于一个特定$T=f(A)$计数的过程：
对于每个$T+1\leq sum\leq 2T$,我们要求出有多少种满足$f(A)=T,\sum_{i=1}^mp_i=sum$的排列$A$
考虑我们先从$n$个数中选出$sum$个数作为环中的元素。
然后我们就考虑怎么把这$sum$个数安排进环里，相当于我们要求出有多少种$sum$个数的有向圆排列划分，满足环的数量为$sum-T$,且不存在大小为$1$的环（这是本题和第一类斯特林数的区别）我们设这个值为$dp[T][sum]$
答案即为:$\sum_{i=0}^k\sum_{j=i+1}^{2i}C_n^jdp[i][j]$
考虑怎么递推出$dp[i][j]$
我们考虑这些圆排列划分，限定这$j$个数字是从小到达放入的。
在放第$j$个数字的时候
$1.$若前$j-1$个数字都已经成二元或二元以上的有向环，那么$j$不能单独成环（单元环是不被允许的），那么$j$有$j-1$种插入方式（有向边数量）
$2.$若有一个数字$u<j$在$j$插入前是单独成环的（最多有一个，若更多那么无论怎么插$j$都会形成单元环），那$j$一定要与$u$成二元环，$u$有$j-1$种可能，其他已成多元环的数字经过重新编号后可从$dp[i-1][j-2]$转移过来与现在决策无关。
因此：$dp[i][j]=(j-1)(dp[i-1][j-1]+dp[i-1][j-2])$
复杂度$O(k^2)$
F.PQ-trees
题面：请参照原题面
$solution$:
首先，先把第一个排列重标号升序的，同时用新标号修改其他排列。一棵子树下的数字一定是连续的一段，$[l,r]$可以在同一棵子树当且仅当数字$[l,r]$在所有排列中都在连续的一段标号中。
假设某个节点$P$对应了一个数字区间$[l,k]$，现在要给它加一个子树$[k+1,r]$，需要满足的条件是$[k+1,r]$在所有排列中都是连续的,如果不再往这个节点上加子树了，要满足的条件是$[l,r]$是连续的。
节点$Q$的情况比较麻烦，它需要满足的条件是$[k+1,r]$是连续的，$[l,r]$是连续的，如果不再往这个节点加子树了，只要这两个限制就可以了。但如果以后还要往这个节点加子树就必须存在一个$z$满足$[k+1，z]$是连续的。
还有：我感觉本质不同的两棵$P-Q$树的限制方法就是，禁止$P$节点作为$P$节点的儿子，这样的$PQ$树只要树形态不同就是本质不同的。但还不会证明。
上面那个$O(n^3)$的$dp$感觉还有好多细节和正确性没想清楚。
这道题还是很难的，也非常有意义，得找个时间把它想清楚写清楚
G.Random walking
一棵$n\leq10^5$的树，有$m\leq2·10^5$次询问，每次给出$u_i,v_i$，问从$u_i$开始树上随机游走，期望游走几步走到$v_i$
$solution$:做两遍树$dp$，第一遍$dp$出：从某个点开始随机游走，期望走几步第一次到达父亲，第二遍$dp$出：从某个点的父亲开始随机游走，期望走几步第一次走到该点，这两种$dp$分别设为$f,g$则每个询问的答案就是$\sum_{u->lca}f+\sum_{v->lca}g$这通过树上倍增即可实现。$dp$时使用无穷等比数列计算期望即可
复杂度：$O(n)$
H.Sasha And Swag Strings
本题极具启发性，将专门为其撰写一篇博客
I.Tree Confrontation
J.Two Airlines
交互题
有一个$n$完全图，边分黑白，但你不知道边的颜色，你可以问交互器$2n$次某条边的颜色，要求找到一条哈密尔顿回路使得顺着这条回路走颜色最多转换一次
$solution$:考虑一直维护一条路径，保证最多之有一个颜色突变点，我们设这个点为$v$，我们每次加入一个点$x$，询问$(x,v)$
若这条边白，则再询问$(x,路径中突变点相连的黑点u)$，否则询问$(x,路径中突变点相连的白点u)$,将原来的路径中$(u,v)$改为$(x,v)(u,v)$，则路径依然最多只有一个颜色突变点，很容易就可以维护颜色突变点的位置