我的学习笔记。
2019年2月2日
Codeforces 1106 E
题意：有$k$个红包，第$i$个红包可以在$s_i$到$t_i$的时间内抢，同时获得$w_i$的钱，但是抢完以后一直到$d_i$都不可以继续抢，$bob$从$1$到$n$的时间内可以抢红包，他的策略是在第$i$个时间点内找$w_i$最大的红包，如果有相同找$d_i$最大的，再相同就随便挑，但是$alice$可以在最多$m$个时间点内打扰$bob$，在$alice$打扰的那个时间点内$bob$无法抢红包，问$bob$能获得的最少钱数。
思路：首先确定$bob$在第$i$个时间点会取哪个红包，把所有红包按题意排好序后遍历一遍，到第$i$个红包时就把$s_i$到$t_i$刷成i，用并查集来实现区间染色，然后考虑$dp$：$dp(i,j)$表示在前$i$个时间点中，$bob$被$alice$打扰了$j$次，$bob$所能获得的最差钱数，然后状态转移方程就分两种情况考虑：
$dp(i+1,j+1)=min(dp(i,j),dp(i+1,j+1))$
$dp(d_{best_i}+1,j)=min(dp(i,j)+w_{best_i},dp(d_{best_i}+1,j))$
反思：题意中加粗的地方。原来只是求了$dp(n,m)$，但其实是$min_{j=0}^m dp(n,j)$，然后还把$j$写成$m$了。
Topcoder 10107
题意：给定一棵树，其中有些点是忠诚的，现在要选k个点，每个选择的联通块都必须包含一个忠诚的点，求包含某个点的概率。
思路：考虑树型$dp$，$dp(i,j,0/1,0/1)$表示$i$号节点为根的子树中选择$j$个，$i$选不选，是所有选择的联通块都是含有忠诚的点，还是只有$i$所在的联通块不含。状态转移方程：
$dp(u,i+j,0,1)=dp(u,i,0,1)\times(dp(v,j,0,1)+dp(v,j,1,1))$
$dp(u,i+j,1,0)=dp(u,i,1,0)\times(dp(v,j,0,1)+dp(v,j,1,0))$
$dp(u,i+j,1,1)=dp(u,i,1,0)\times dp(v,j,1,1)+dp(u,i,1,1)\times(dp(v,j,0,1)+dp(v,j,1,0)+dp(v,j,1,1))$
解释：$v$是$u$的儿子，$i$、$j$是枚举的$u$在$v$之前的儿子所构成的子树和$v$所挂的子树中所选的数量。为什么没有$dp(i,j,0,0)$？因为如果这个节点根本不选，就不可能有这个点所在的联通块。
反思：这个方程重写了几次才写对。属思路不明确。
2019年2月3日
Codeforces 1105 E
题意：给你m个事件，每个事件可能是以下两种之一：
- $1$，代表此时可以更改用户名
- $2$ $s$，代表$s$来查看是否用户名与其名字相符
一共有$m\leq40$个人，如果一个人每次看到用户名都与其名字相符，则他会开心，问怎么更改用户名使得开心的人最多？
思路：看每次$1$后面连续的$2$，把其中的人两两连边，题目转化成求此图的最大独立集。看到$m$的范围较小，且不能直接做，那么考虑折半搜索。把人分成前一半和后一半，枚举出前一半在后一半有不能取的限制下的最大能取的个数，枚举后一半所取的是哪些即可。
反思：在求对于前一半固定时后一半可以取的最大集合时由于反复求亦或运算，导致本该为$0$的位反成了$1$，造成答案错误，竟卡了一整天
2019年2月7日
反思
一直都没有几场打得好的比赛。
在比赛时会出现一些突发情况，发生之后没有立刻冷静下来继续认真做题，而是慌乱之后就各种乱来。
这里犯了第一个错误：急躁
此问题在很早前就出现了，之所以这么长时间都没有解决是因为我对自己不够严格
这些突发情况分两种：
- 外界情况：比如网络问题。在这些根本算不上问题的问题中还不能保持镇定就是学习方法的问题
- 自身原因：在这场比赛中，我$A$题有一次$wa1$，原因是我把半成品提交上去只是为了检验我是否能连上网，这是非常不应该的，再怎么样也得把程序写完、测完再交吧，由此可以看出我对这个比赛的重视程度。
这是第二个错误：态度
我对这个比赛的态度还像之前一样轻视，觉得就是一场比赛而已。然而其实对于每一场比赛，如果我都不重视，谁会？
以后的改进：
将每一场比赛看成像NOIP那样重要的比赛
遇到任何突发情况都不能慌，要一如既往地认真、专心的比赛。
不仅是比赛，题也是一样。做题同样需要好的方法和态度。
2019年2月8日
Codeforces Round 1110
这场比赛只做了$A$、$B$、$C$，排名$905$，不好。
主要的问题在$D$题上，有$505$人做出，但我没做出来。
考虑的时候方向不对，一直抠一个思路不放，然后就一直做不出来。
虽然我中间也考虑过其他的思路，但是都没有思考完善，于是就一直在给我原来的方法加补丁。
Codeforces 1110 D
题意：给定一个序列，问最多可以把该序列分成几个满足下列两个条件之一的三元组：
- 这三个数字相同
- 这三个数字为连续的三个数
思路：首先因为三次取连续可以分成三次取相同，所以最多有两次连续。然后考虑$dp$：$dp(i,j,k)$表示到了$i$这个数，$i$作为连续的三个数的中心取了$j$次，$i+1$作为连续的三个数的中心取了$k$次，可以取的最多的三元组个数。转移方程：
$dp(i,k,l)=max(dp(i,k,l),dp(i-1,j,k)+l+(a_i-j-k-l)/3)$
反思：此题我在比赛时想的方法是考虑先取数值相同的三元组，看每个数字取完后还剩下多少（猜了个肯定不超过$5$的结论（其实是不超过$9$），然后发现得不断地加补丁修正，因为自己也在不断发现比原来认为的范围更大的反例），然后就陷入其中出不来了。
Codeforces 1110 E
题意：给定两个数组，从第一个数组开始，每次可以挑选一个数，把它变化成左右两数之和减去原来的数，问是否可以将第一个数组转化成第二个。
思路：
结论：两个数组可以互相转化的充要条件是它们差分后的数组排序后相同并且它们第一个数相同。
证明：
先证明一个引理。
引理：两个数组可以互相转化的必要条件是它们都能转化成同一个数组。
证明：假设A转化成B，C也转化成B，由于操作可逆，于是可以从A转化成B再转化成C。$\square$
证明原结论的充分性。
看某一次操作。
从$c_1,\dots,c_{i-1},c_i,c_{i+1},\dots,c_n$更改到$c_1,\dots,c_{i-1},c_{i-1}+c_{i+1}-c_i,c_{i+1},\dots,c_n$
差分数组从$c_2-c_1,\dots,c_i-c_{i-1},c_{i+1}-c_i,\dots,c_n-c_{n-1}$更改到$c_2-c_1,\dots,c_{i+1}-c_i,c_i-c_{i-1},\dots,c_n-c_{n-1}$
可以看出，它们排序后的结果定然是一样的。
证明原结论的必要性。
如果这两个差分数组排序后是一样的，以上文的方法可以用类似冒泡排序的方法把差分数组变为有序的，因为它们第一个数相同，所以原数组也相同。
$\square$
按照结论直接做就可以了。
2019年2月9日
Codeforces 1110 D FST分析
dotorya、FizzyDavid、MofK、gamegame、matthew99、chokudai、eddy1021、DBradac、_Happy_New_Year_、edisonhello、Baneling2、skylinebaby、QWE_QWE、Suzukaze、LJC00118、ATS、Jayce132、sava-cska（$wa35$）：考虑$i$这个数留下了多少个，但把最多留下的范围改成$9$竟然就过了！
cz_yixuanxu、PhoenixEclipse、zjczzzjczjczzzjc、Qing_Yang、mitterr1999、receed、Lily、BiuBiuBiu_（$wa40$）：把$m$写成$n$了
panole（$wa14$）：把$9$写成$3$、把$m$写成$n$了
icecuber（$re23$）：$dp$状态内会出现远大于开的数组范围的值
gtrhetr（$wa17$）：把最后一个的扣的数量加到了倒数第二个上
Atcoder Round yahoo-procon2019-qual
这场比赛做了$A$、$B$、$C$、$D$，排名$333$。
主要问题在$D$上，提交了$3$遍才过。属于考虑问题不完整。
Atcoder yahoo-procon2019-qual D
题意：给你$L$个耳朵（？？？），以及一条范围从$0$到$L$的数轴，你可以选择一个出发点，从该点开始随意走动，如果经过了$i-0.5$这个点，则会给第$i$个耳朵的数值$+1$，每个耳朵都有一个最终的要求值，你可以通过增加或减少一个耳朵的数值来达到要求值，问最少更改的次数。
思路：
走的路线是这样的（或者左右颠倒）：
首先往左一段距离；
再向右一段距离（超过原点）；
再向左一段距离（不超过原点）。
然后就可以预处理出三段分别的最小值：
- 最左点到原点（可给耳朵赋的值是非$0$偶数）
- 原点到结束点（可给耳朵赋的值是奇数）
- 结束点到最右点（可给耳朵赋的值是非$0$偶数）
然后就可以稍微递推一下了。
反思：比赛时的思路第一开始都没考虑到最后还可能折返一段距离，于是就挂了第一次，第二次是$i+1$写成$i$了（可以这么说，但是我以为的错误是还要加上一段不超过最右点的向右折返，然后加上了个没用的东西）。所以第一开始最好还是考虑更完善一些。
2019年2月10日
Codeforces 499 D
题意：给$n$个曲子，每个曲子每一秒有$p_i$的几率可以被猜出来，过了$t_i$秒肯定能被猜出来，猜完第$i$首歌立即播第$i+1$首，问$T$秒内期望猜多少首。
思路：考虑$dp$：$dp(i,j)$表示在第$j$个时间点正好猜出第$i$首歌的概率
转移方程：$dp(i,j)=dp(i-1,j-t_i)\times(1-p_i)^{t_i-1}+\sum_{x=1}^{t_i-1}dp(i-1,j-x)\times(1-p_i)^{x-1}\times p_i$
可以看出，这个肯定是要超时的，所以对$\sum$内进行优化
原优化：记录两个变量$sum$和$mul$表示$\sum$内的式子结果是$sum\times mul\times p_i$，然后在$j+1$后$sum+dp(i-1,j-1)/mul-dp(i-1,j-t_i)/(mul/(1-p_i)^{t_i-1})$，$mul\times (1-p_i)$即可。
评：这个优化看起来很对，但是由于$mul$实在太小，浮点误差导致变成了$0$，所以不行。
优化：类似滚动哈希，记录$sum$表示$\sum$内的式子结果是$sum\times p_i$，然后在$j+1$后$sum\times (1-p_i)+dp(i-1,j-1)-dp(i-1,j-t_i)\times (1-p_i)^{t_i-1}$即可。
2019年2月11日
Codeforces Round 1114
这场比赛做了$A$、$C$、$D$、$E$，排名$134$。
$B$题做了很长时间，好不容易最后一分钟$Pretest\ Passed$了，但是又$FST$了。。。
$C$题$wa7$了一次，因为爆$long\ long$了
$E$题$wa1$了一次，因为最后的输出格式错了
Codeforces 1114 B
题意：给$n$个数，把它们分成$k$段，求每段最大的$m$个数最大总和。
原思路：二分每段最小的数，然后贪心地选让每段最小的数大于等于这个，看是否可以。让每段最小的数最大。
评：首先，这玩意会$tle$。其次，这玩意会$wa$。
思路：最大的$k\times m$个数是肯定要被选中的，那么把它们前$m$个分在第一段，$\dots$，最后$m$个分在最后一段即可。
反思：比赛的时候看着不会，于是硬做，然后搞出来了个这么个东西。。。
Codeforces 467 D
题意：给$m$个单词，以及$n$个置换关系，问将$m$个单词替换多次后其中所含的最少的$R$的数量以及满足这个数量的最短总长度
思路：首先将置换关系构图，然后进行强连通分量分解，为每一个强连通分量保存最小的答案，然后$dp$把一个子$dag$的答案求出即可。
$wa$了$3$次，前$2$次是因为$tarjan$写错了，另一次是因为没开$long\ long$。
2019年2月13日
Codeforces 86 C
题意：给$m$个串，要构造长度为$n$的串，而且必须由这些模式串们覆盖（可以重复），问可以构造多少种。
思路：首先构造AC自动机，然后$dp(i,j,k)$表示现在到了要构造的串的第$i$位，匹配到了AC自动机的第$j$个节点，最后$k$位还未被覆盖的种数。
转移方程：如AC自动机的第$j$个节点是某个模式串的结尾且这个模式串的长度大于$k$，那么
$dp(i+1,nxt_j^c,0)+=dp(i,j,k)$，否则$dp(i+1,nxt_j^c,k+1)+=dp(i,j,k)$
2019年2月14日
Codeforces 17 E
题意：给一个串，求其中回文子串交叉的对数。
思路1：用哈希解决。首先求出每个点左右最长的回文串（要分奇数长度和偶数长度），然后记录经过每个点的回文串的个数，以及它们是在回文串的前半段还是后半段（代表着对于当前节点这个回文串是刚刚覆盖到它还是将要消亡），然后到每个节点的时候将新经过当前这个节点的回文串两两配对，并且将经过当前这个节点但没有消亡的回文串与新经过当前这个节点的回文串配对，更新经过当前节点的回文串。
思路2：用回文树解决。在回文树中记录在每个节点结束的回文串个数，然后反着建一遍树，求出在$i$及$i$后开始的所有回文串，再正着建一遍，把在$i$结束的回文串和在$i$后开始的回文串一一配对，这些是永远搭不上边的。再用所有回文串一一配对的数量减去这个数量即可。
2019年2月15日
Codeforces 526 D
题意：给一个字符串，求每个前缀是否能表示成$A+B+A+B+\dots+A$（$k$个$A+B$）的形式。
思路1：求出所有前缀的哈希值，以便求每个子串的哈希值。然后枚举$A+B$的长度，二分$A$的长度，用哈希检查一下字符串是否相等即可。
思路2：求出KMP的$fail$数组，然后枚举前缀的长度$len$，看该前缀的最小循环节$min=len-fail_{len}$（因为$A+B+A+B+\dots+A+B+A$中前缀$A+B+A+B+\dots+A$与后缀相等，所以$A+B$的长度就是如此求出），
则$|A+B|=q\times min$，
所以$len=k\times|A+B|+|A|=k\times q\times min+x\ (0\leq x\leq q\times min)$。
然后得$k\times q\times min\leq len\leq (k+1)\times q\times min$。
所以$\frac{len}{(k+1)\times min}\leq q\leq \frac{len}{k\times min}$
那么既然$q$为整数，则$q$在$[\lceil \frac{len}{(k+1)\times min}\rceil,\lfloor \frac{len}{k\times min}\rfloor]$中。
进行判断即可。
思路3：同样求出KMP的$fail$数组。然后构建$i$跳转$2^j$次$fail$后得到的位置的倍增表，枚举前缀的长度$len$。
对于一个前缀，$|A+B|$最极端的情况是$A$为空或$B$为空，两种情况分别$|A+B|$为$\frac{len}{k}$和$\frac{len}{k+1}$，所以可以求出$|A+B|$的范围。下面只要看通过倍增表是否能从$len$跳至$len-|A+B|$的范围即可。
思路4：$Z_Algorithm$求出$Z$数组表示与前缀向后最长匹配长度，然后枚举$|A+B|$，判断是否循环$k$次，再将最后一个$A$可取的最长长度通过$Z$数组算出，差分区间修改每一个前缀是否可以即可。
2019年2月16日
Codeforces 696 D
题意：给$n$个串，每个串有一个权值$a_i$，现在要构造一个长度为$l\leq 10^{14}$的串，如果其中包含了第$i$个串，则会得到$a_i$的奖励，问最多奖励值。
思路：首先建立AC自动机。然后考虑$dp$。$dp(i,j)$表示当前到了构造串的第$i$位，匹配到了AC自动机上的第$j$个节点，最大权值和。
转移方程：$dp(i+1,nxt_j^c)=max(dp(i+1,nxt_j^c),dp(i,j)+val(nxt_j^c))$
然后因为$l$实在太大，所以考虑用变种矩阵乘法转移。
考虑建立转移矩阵$M$，其中$(j,nxt_j^c)$这一位为$val(nxt_j^c)$。
然后矩阵“乘法”中将加号改为取$max$，乘号改为加号即可。
Atcoder ARC060 F
题意：给一个串，求将其分成最少的没有循环节的串的种数。
思路：先求KMP的$fail$数组。然后发现最少的串数只有三种可能：$1$、$2$、$n$。
然后就可以用KMP找原串的循环节，如果原串没有循环节，那么不用分。如果原串的循环节为$1$，则要分成一个一个的，如果循环节为$2$，则要看每个前缀和后缀是否有循环节，如果对于一个前缀即与之相邻的后缀都是无循环节的，那么答案数要$+1$。
2019年2月18日
Codeforces Round 1117
这场比赛做了$A$、$B$、$C$、$D$、$E$，$div.2$排名$31$，加上$div.1$排名$64$。
主要是$A$题卡了很久，直到第$52$分钟才做出来，思路固化了，一直没想到最大平均值的区间就是只含有最大值的区间。幸好节奏没有受到太大影响。
最后去肝$G$，最后一分钟一把过了样例，就赶紧交，结果$ce$了。。。实在是。。。是因为我定义重数组，而条件编译使我看不出有问题（这段快读的代码本机不要）。。。
然后改掉，$tle8$，因为我构造的那个”类$treap$”并不是期望$O(log_2\ n)$深度的。。。
Codeforces 1109 C
题意：现在有个碗，每时每刻其中的水量都会加一个整数（可以为负）。
给$n$个询问，询问有$3$种类型：
- $1\ t\ s$：将从第$t$秒开始水量增加的速度改为$s$。
- $2\ t$：删除第$t$秒对水量增加速度的改变。
- $3\ l\ r\ v$：考虑从第$l$秒到第$r$秒对水量增加速度的改变，并假设初始时水量为$v$，问什么时候水量降至$0$。
思路：一看就是道数据结构题。
前两个操作其实都是改变一个时间段的水量增加速度，即区间修改，用线段树维护每一秒的水量增加速度，每个区间和就是一段时间中水量的变化情况。
由于时间段十分长，离散化用到的（即改变过水量增加速度的）时间。然后就要注意了区间不是等长的，求和时要带上一个系数表示这个区间的长度。
然后考虑第三个操作。
这里有两种处理方法，个人写的第一种会TLE，P.S.我写的版本也过了。其实是我线段树的问题：
在我的线段树的下推操作中，我只是将当前的节点的值根据该区间赋的值来更改，并且把标记下推到了下一层节点，但是跑到下一层节点后还得再下推，即使到了最后一层也是如此。所以，最后一层的下推操作就是浪费时间，几乎浪费了两倍，那么就将下推操作改成把两个儿子节点的值都更改了即可。
而别人（ko_osaga）就过了，可能是我自带大常数吧。
- 第一种是二分第一次降至$0$的位置$l\leq i\leq r$，判断$[l,i)$区间中最小前缀和$+v$是否小于等于$0$，如果如此则说明到$i$为止水量降为$0$过了，则把二分的右边界缩小，否则将二分的左边界扩大。
- 第二种是在线段树上二分。假设现在在线段树的$[a,b)$区间，其中点为$mid$，如果$[a,mid)$区间中最小前缀和$+$当前所查的$v$小于等于$0$，则说明在$[a,mid)$中水量已经降为$0$过了。否则必须在$[mid,b)$中才使水量降为$0$，则需要使$[mid,b)$中的最小前缀和加上$[a,mid)$的和$+v$小于等于$0$，则$[mid,b)$所查的$v$为$v+[a,mid)$的和。
然后就是要考虑怎么求一个区间的最小前缀和了。
在线段树上多记录一个数据$mn$，表示这个节点表示的区间中的最小前缀和。
在对整个节点所表示的区间都刷上一个值时，该节点的$mn$只可能是两种情况：$0$或该节点的和。因为如果刷上的那个值$<0$，那么该节点所表示的区间前缀和递减，则肯定取该节点的和为$mn$，否则区间前缀和递增，必须取$0$为$mn$。
在修改结束的上推操作中，该节点的$mn$应该取左节点的$mn$和右节点的$mn+$左节点的和的最小值，因为该节点的最小前缀和可能跨左节点的区间也可能不跨。
每个操作的具体处理：
用一个$set$保存所有的更改水量增加速度的事件。然后找到当前事件后一个是什么。把中间一段都修改成当前要修改到的速度即可。
找到当前事件前一个是什么。把当前事件到其后一个的中间一段修改成前一个所修改到的速度即可。
按照上面所说二分即可。
还有一种方法是用一个$treap$来维护所有的更改操作，按照发生的时间排序（Um_nik）。
既然$treap$的每个节点代表了一个更改操作，那么这个节点所挂的子树就代表了一个区间（一堆操作中最早的到最晚的）。
在$treap$的每个节点中需要维护以下信息：
- 这个节点所存的更改操作的时间、将要改到的速度
- 这个节点所挂子树所代表的区间的开始时间和结束时间，以及最后一个时间点的水量增加速度
- 从这个子树表示的区间的开始到结束每个时间点的水量增加速度之和
- 这个子树表示的区间的最小前缀和
然后$split$和$merge$两个操作都和正常的$treap$差不多，但是需要增加一个$pushup$操作来更新和与最小前缀和：
该子树的和就是左子树的和$+$右子树的和$+$左右子树都没有计算到的部分
左右子树都没有计算到的部分是从左子树的最后一个操作到当前节点的操作再到右子树的第一个操作的区间。
如果没有左右子树，则需要特判一下。
每个询问的处理：
插入：将$treap$分成小于$t$和大于$t$两部分，然后把新加入的节点放在中间，$merge$回去。
删除：将$treap$分成小于$t$、等于$t$、大于$t$三部分，然后把中间那个节点拿去，$merge$回去。
查询：将$treap$分成小于$l$、$l \leq x \leq r$、大于$r$三部分，然后在中间的那个部分中二分：
如果当前节点的左子树的最小前缀和$+v$小于等于$0$，则在左子树里找；
如果当前节点的左右子树都没计算到的部分加上左子树的和$+v$小于等于$0$，则算一下等于$0$时在哪，直接输出。
否则就肯定在右子树里了。现在的$v$需要加上左子树和加左右子树都没计算到的部分。
然后这种方法常数稍微比线段树小一点？
2019年2月21日
Codeforces 1114 F
题意：给你一个序列$a_{1\dots n}$，以及$q$次查询，每次查询有两种格式：
- TOTIENT $l$ $r$：求出$\phi(\Pi_{i=l}^ra_i)$。
- MULTIPLY $l$ $r$ $x$：将从$l$到$r$的所有数乘上$x\leq 300$。
处理每次查询。
思路：首先我们知道设$x=\Pi_{i=1}^np_i^{e_i}$，则$\phi(x)=x\Pi_{i=1}^n\frac{p_i-1}{p_i}$。
所以就可以想到记录每一个数的质因子有哪些。
由于这个序列的每个数都很小（$a_i\leq 300$），所以在此范围内的质数也不多（$62$个），然后就可以用一个$long\ long$存下了。
然后考虑高效地处理区间乘。
可以用分块和线段树来解决。（我只写了分块）
将原序列分成几块，每一个块的大小是$B$，然后对于每个块存储以下信息：
- 这个块所有数的积以及该乘积所含质因数
- 这个块对于所有数同时乘的数以及这个数所含质因数
- 这个块中每个数的值（这个只在边角的修改上要存）以及这个数所含质因数
每个操作的具体处理：
- 修改：首先要改区间两边未在整块内的边角的每个数的值和整块的积，然后再将中间块的整块的同时乘的数都改为需要更改的数。
- 查询：也是一样，现将区间两边的数乘上整块都要乘的数乘到答案里，再将中间块整块的乘积乘进答案。
然后就会发现如果要更改整块的积时需要求一个数的$B$次幂，那么就预处理一下即可。
然后具体的实现中还要注意一下一点点细节。
2019年2月23日
Codeforces 142 C
题意：给一个$n\times m$的空矩阵，求里面放最多的可旋转的$T$字形的个数，并输出方案。
思路1：
由于$n$和$m$比较小，所以可以尝试搜索。
对于每一个格子，尝试$T$字形的$4$种旋转方式，然后看$T$字形覆盖到的格子是否已经被覆盖了，如果没有那么就可以进入下一个格子。
这样是会$TLE$的。所以考虑最优性剪枝。对于这个格子，如果已经放的$T$字形的个数加上后面能放的最多个数（剩下的空格子/5）还不比最佳答案大，那么就不必继续了。
想一想后发现其实我们还能剪掉更多的枝叶。因为$T$字形的特殊性，它在放置的时候是不可能把能放的所有格子填满的，而是会浪费一些格子，所以我们有了一个大胆的想法：每个$T$字形会实际占据大于5个的格子数，这里通过调参得到6.5个格子的效果最好。所以就这样搜过去了。
思路2：
由于$n$和$m$比较小，所以可以考虑状态压缩动态规划。
首先假设当前处理到$(x,y)$格子。我们知道每一个$T$字形会占据$3\times 3$的空间，然后就可以想到将$(x,y)$一直到$(x+2,y+2)$是否被$T$字形覆盖的情况都存下，即存$2\times m+3$个格子，也不会出现空间或时间不够的情况。
然后就可以想出$dp$状态和转移方程了：$dp(x,y,mask)$按照之前所说，考虑到$(x,y)$这个格子，$(x,y)$到$(x+2,y+2)$的覆盖情况在$mask$中，最多放的$T$字形数量。
方程也就是考虑这里$T$字形放哪一种旋转的方式，将$mask$中相应的位置更改是否被覆盖的状态，注意需要判断一下是否原来没有被覆盖，如果已经被覆盖了就不能放。
最后就是要输出方案的问题了。
有两种方式：
- 像正常的$dp$一样对于每一个状态记录$prev$表示当前状态从哪一个状态转移来，从初始状态一直通过$prev$走到最终状态。
- 类似于重做一遍$dp$，看当前的最大值由哪一个状态转移而来，然后一直走到最终状态。
Codeforces 111 C
题意：给$n\times m$的网格，每个点上有一个蜘蛛，每个蜘蛛可以向上、下、左、右走一步或者不动，问最多能存在多少没有蜘蛛的点。
思路1：
首先因为$n$和$m$中小的那个不可能超过$6$，所以钦定$m < n$（因为如果$n$和$m$互换不影响答案）。
然后就可以考虑状压$dp$了。
首先我们看$(x,y)$这个点上面可爱的小蜘蛛的去向。它可能会往上走，到$(x-1,y)$；也可能向下走，到$(x+1,y)$；也可能向左右走；所以就会发现在不断向下一个点移动的过程中，对于$(x,y)$有影响的是从$(x-1,y)$到$(x+1,y)$的$2\times m+1$个点。所以$dp$状态和转移方程都可以求出辣：$dp(x,y,mask)$表示到了$(x,y)$这个点，$mask$表示从$(x-1,y)$到$(x+1,y)$的点是否是蜘蛛集合点。
转移方程和$(x,y)$上的蜘蛛往哪个方向去走有关，或者它停在原地，它去的那个点必须是蜘蛛集合点，如果原来不是，那么答案必须加1。然后转移到下一个点即可。
思路2：
首先还是钦定$m < n$。
然后还是考虑状压$dp$，其状态为$dp(x,mask)$。表示第$x$行时的状态。
这里$mask$保存的是当前行和上一行的所有的蜘蛛是否已经有地方去，然后转移的时候用$dfs$枚举一行中哪些点作为集合点（这里需要枚举所有集合点的集合），同时将其四周的点的状态赋为有地方去，然后让当前行的上一行不要有没地方去的点，继续考虑下一行的$dp$。
思路3：
钦定$m < n$，考虑状压$dp$，其状态为$dp(x,mask)$。
这里$mask$保存的是当前行与上一行的集合点集，$dp$的值是考虑最多的空闲点的个数。
转移的时候枚举这一行新的集合点集以及下一行的集合点集，然后判断是否有当前行原来是集合点而现在不是的，有没有当前行没地方去的点，如果都没有就可以进入下一行的$dp$。
总结：
这3种思路较快的是思路1、2，然后较慢的是思路3，因为思路1的时间复杂度是$O(n\times m\times 2^{2\times m+1})$，思路2的复杂度是$O(n\times2^{3\times m})$，思路3的复杂度是$O(n\times2^{4\times m})$。
由此可见，状压$dp$的状态选择方面，对于复杂度是有非常大的影响的。
2019年2月24日
Codeforces Gym 100725K
题意：给定一个初始全0的序列，然后给$n$个查询，每一次调用$Insert(L_i,i)$，其中$Insert(L,K)$表示在第L位插入K，如果第L位已经有值了就会先调用$Insert(L+1,A_L)$（其中$A_L$表示第L位上的值），再将$A_L$赋为K。问经过查询后序列的模样。
思路：首先将题意抽象成每次找到从第L位开始第一个0，并将其“拖”回第L位，然后将其更改为K。这个操作很明显可以用FHQ Treap完成，只要在每个节点处新维护一个值表示当前节点的子树中的值有多少个为0。然后对于每一个操作先将从L开始的后缀split出来，然后在Treap上二分：如果当前节点左子树上有0，那么在左子树中找，如果当前节点为0，答案就是当前节点，否则在右子树中找第一个0。然后找到第一个0在树中的排名后将其split出来更改一下信息再放到正确的位置即可。
反思：这道题我WA1了一次，因为输出的格式不对，没有输出最后序列的长度，所以。。。这其实是个很严重的问题。即使真的写出来是对的，那么格式一错，全盘皆输。
2019年2月25日
Codeforces Round 1129
这场模拟比赛做了$A1$、$A2$、$B$、$C$，$Div.1$排名40。
$A$题是道贪心，可以考虑每一个站点是分开来的，把目的地最小编号的留到最后，所以答案稍微算一下就行了。
$B$题是道找规律，首先可以很容易地发现只要前面弄个负数的开头，错误算法就会忽略掉这一个值，所以利用这个来构造答案。（最讨厌构造题了）然后推导一番式子就会发现如果我们将第一个值放-1，则
$\sum_{i=2}^na_i=k+n$，
再更改一下形式（因为我们不知道n）
$\sum_{i=2}^na_i-1=k+1$。
然后就可以做出来了。
$C$题一眼不字符串吗，再一眼不dp吗，然后就写了个区间dp上去，发现没法判重了，就又写了个set装哈希值。。。（这里为下文的TLE作铺垫）把set改成哈希表，竟离奇MLE？？？改小一点数组就可以过辣。其实不难？
2019年2月27日
Codeforces 1129 C
题意：给一个0/1串，问它的每一个前缀中的每一个子串能解析成莫尔斯电码的串的种数。
思路：首先对于这个串构造后缀自动机，那么从起点走到每一个节点的每一条路径都代表了这个串的一个子串，所以考虑以后缀自动机上的节点作为dp的对象，即$dp(i)$表示考虑第i个节点所表示的子串们，能够解释成多少种串。
转移方程就考虑现在在u节点，$dp(go(u,i))$可以加上$dp(u)$的值。
求答案的时候需要注意。我们需要在插入字符的时候就将每一个节点所对应的前缀的第一次出现位置给记下来，然后对于每个节点它父亲肯定会在它出现的地方出现，所以就将标记上推到link。
然后对于每一个节点将这个节点的dp值加到它第一次出现的地方，然后输出的时候求个前缀和就可以了。
2019年2月28日
Codeforces 113 B
题意：有一个母串$S$以及两个串$S_{begin}$和$S_{end}$，问$S$中以$S_{begin}$为开头并且以$S_{end}$为结尾的不同子串的个数。
思路1（后缀自动机）：
首先肯定要把后缀自动机构建出来（第一次一遍敲对后缀自动机祭），然后我们考虑$S_{begin}$（和$S_{end}$，是对称的，不做考虑）是不是在S中作为一个子串出现，如果出现了那么看它所对应的节点是哪个，打个标记（这个操作就是在自动机上沿着$S_{begin}$的每个字符的那条边走，最终走到哪个节点就是$S_{begin}$所对应的节点。）
然后找S的每一个长度为$|S_{begin}|$的子串，在自动机上走一遍，如果最终的节点是$S_{begin}$所对应的节点，那么就说明$S_{begin}$在此出现了，在这一位上打标记。
枚举要求的子串的开头结尾位置，如果开头的时候$S_{begin}$出现了，且在结尾的时候$S_{end}$出现了，那么这个子串就是属于答案的。将这个子串对应的节点的这个长度的标签打一下。（这里很需要注意！！！我在写的时候直接是将这个节点的标签打上了，这样非常不对，因为一个节点的定义是长度连续的一些子串们！！！如果我们只是将这个节点打上标签，则会区分不出来长度不同的子串，导致答案减少很多。因此WA15了两次！）
看每个节点打了多少标签就好了。
思路2（后缀自动机）：
首先也是构造后缀自动机。
然后我们可以找到$S_{end}$在自动机上对应的节点是什么。既然这个子串以 $S_{end}$为结尾，那么肯定是$S_{begin}$+$S_{end}$的一个后缀或$S_{begin}$+（一堆东西）+$S_{end}$。我们希望保证$S_{begin}$完整以便计算答案。所以我们需要将$S_{end}$的答案加到$S_{begin}$头上。
这里用的方法是这样的：
首先将end的值加到parent树的子树中（parent树就是将所有节点的link指向的值向它们自己连边后的树），
其次将所有的节点的值加到go的dag中这个节点的所有父亲们头上。
这样做的结果就是每一个节点$u$的值就是从$u$表示的某个子串开始之后以$S_{end}$为结尾的不同子串个数
那么答案就应该是$S_{begin}$所对应的节点。
但是如果直接这样交上去会$wa30$，说明还有一些问题。
对此，freak93在最后做了一些处理，使得他的程序可以AC：
按照$S_{end}$的顺序在自动机上跑，如果当前节点已经跑到了$S_{begin}$应该到的位置，但是长度却不对，就是说跑到了这个起始串对应的节点的其它子串内，肯定不应该取。否则如果已经跑到了长度为$|S_{begin}|$的节点，但是并不是$S_{begin}$所对应的节点，那么就肯定得跑到现在已经到的串的后缀继续看（为什么会是后缀啊。。。我觉得应该是前缀？为后面的反例埋下伏笔）
应该就是这样的？看了一天不算特别懂。。。（这里完全不对。。。
P.S.：这里的做法其实是看$S_{begin}$是不是$S_{end}$的一个子串且不是它的前缀，如果是的话就说明从$S_{begin}$所代表的节点可以走到$S_{end}$所代表的节点，
要减去一些不对的答案，比如$S_{begin}$在$S_{end}$中出现的次数，还有如果是$S_{begin}$在之前出现过，即说明真正是有答案的，他应该不更改答案，但是他成功地减去了之前求出来的的答案$\times$出现次数，所以。。。（这个方法真的很不好想啊。。。正常人不会想这种吧。。。可能他异于常人。。。
所以就被我的反例干掉了
注：反例（对于freak93在CF上AC的版本）：
1 | aabaab |
这个的答案应该是1，但是这个程序输出了0。
我感觉好像他的后缀自动机敲错了
不是他的后缀自动机错了，而是我的调试语句写错了以至于我以为后缀自动机错了。。。
肯定是他最后修改对于$wa30$的错误的步骤错了（肯定不是选择跳到后缀嘛）（错误在上面说了）
思路3（后缀数组）：
先用$O(nlog^2n)$的naive的做法求出后缀数组（就是在正常求的每一个$2^h$的阶段都直接sort）
然后把高度数组给求出来（我也不知道什么原理。。。反正求出来的就是排名为i的后缀和排名为i+1的后缀的最长公共前缀辣）
然后暴力（这个很有个性）地求出$S_{begin}$和$S_{end}$出现的位置们。
再想怎么补充不漏地记录答案。首先以i位置开始的子串肯定会和以i-1位置开始的子串有一段重复的，而这段重复的应该已经在i-1的时候算过了，所以i和i-1开始的后缀的最长公共前缀（高度数组）这一段不应该被i开始的子串记录。那么就很简单辣
2019年3月2日
Codeforces 1110 D
题意：给$n$个麻将，每个麻将上有一个$1..m$的整数$a_i$。
现在要将这些麻将们分成一个一个三元组，有两种情况：
- $[i-1,i,i+1]$
- $[i,i,i]$
然后问最多能将这些麻将们分成多少个三元组。
思路1：
结论：对于每一个三元组$[i-1,i,i+1]$，其出现的次数不会超过两次。
证明：
我们如果有$3$个$[i-1,i,i+1]$这种三元组，那么我们可以将其转化成$[i,i,i]$、$[i-1,i-1,i-1]$、$[i+1,i+1,i+1]$这$3$个三元组，得到同样的效果。
那么就可以考虑$dp$了。
考虑$dp(i,j,k)$表示当前已经到了第$i+1$个位，$[i-1,i,i+1]$出现了$j$次，$[i-2,i-1,i]$出现了$k$次，最多可以形成的三元组个数。至于状态为什么是这样呢，就是想我们的$i$麻将被分到了哪些三元组中，其中和前$i+1$个有关的就是这两个。
然后转移的话枚举$[i,i+1,i+2]$这个三元组出现的次数$l$，然后$i$麻将剩下可以供$[i,i,i]$的三元组使用的数量就是$cnt_i-j-k-l$，将$dp(i+1,k,l)$赋成$dp(i,j,k)$加上这个值$/3$再加上$l$就行了。
思路2：
我们不考虑$[i-1,i,i+1]$出现了多少次，我们只考虑被$[i,i,i]$的三元组用过了之后的$i$麻将还剩下多少个。事实证明这个不会超过$9$个。为什么呢？首先我们的$i$被$[i-2,i-1,i]$用了最多两次，$[i-1,i,i+1]$用了最多两次，又被$[i,i+1,i+2]$用了最多两次，再剩下$[i,i,i]$一次的余量。
然后也是考虑$dp$。$dp(i,j,k)$表示当前到了第$i$个麻将，$i-1$还剩下了$j$个，$i-2$还剩下$k$个。然后转移的时候枚举现在对于$[i-2,i-1,i]$这个三元组用$l$个，肯定是小于等于$j$和$k$的，那么再看$cnt_i$用了$l$个后还剩下多少，剩下的如果全用$[i,i,i]$还剩下多少，记这个值为$x$，再看如果少用几个$[i,i,i]$变成了多少，是$x+3y$个，其中$x+3y$应该小于等于$cnt_i$和$9$。
然后转移到$dp(i+1,k,x+3y)$就好辣。
Codeforces 111 C
思路：我们考虑状压$dp$。$dp(i,mask0,mask1)$表示现在我们到了第$i$行，第$i-1$行的点中$mask0$内的的都被十字覆盖过了，第$i$行的点中$mask1$内的点都被十字覆盖过了，最少的十字数量。
现在枚举以第$i$行为中心的十字有哪些，存在$mask2$中。然后必须的是第$i$行的十字必须将$mask0$中可能有的一些空缺填满，然后并且会将$mask1$中的$mask2$中的点及其左右的点覆盖。这里可以用一种很简单的方式来表示$mask2$中的点及其左右：$mask2|mask2<<1|mask2>>1$。
然后转移一下就很简单了。
Topcoder 10524
题意：给一个$n\times m$的棋盘，上面有一些格子是白色的，需要被一些俄罗斯方块们覆盖，俄罗斯方块有$4$种：
然后这些图案不能重叠或超出边界，并且每一个图案有无限个。问最少要用多少个图案来覆盖原图。
思路：由于$m$比较小，所以我们考虑状压$dp$。
考虑$dp(x,y,mask)$表示当前在$(x,y)$这个位置，$mask$表示从$(x,y)$开始$m+2$个格子是否被覆盖的状态，最少需要用的图案数量。
之所以这样是因为绿色图案是最多需要$(x+1,y+2)$这个格子，所以$(x,y)..(x+1,y+2)$这$m+3$个格子按理说都要记录，但是$(x+1,y+2)$在$(x,y-1)$的时候根本不会去更新，所以直接记录$(x,y)..(x+1,y+1)$这$m+2$个格子就可以了。
然后考虑转移。首先考虑这$4$种图案所对应的$mask$需要更改的位置。
- $0、1、2、3$
- $0、1、m+1、m+2$
- $0、1、m、m+1$
- $1、2、m、m+1$
然后就可以更改状态到$nmask$了。这里其实可以预处理出每一个图案对应更改的$mask$，加快更新速度。
还有一种可能是这个格子就不放图案，那么必须要判断$mask$的第$0$位是否已经被覆盖或者是黑色格子不用被覆盖，如果不行就不能转移。
写的时候需要特别注意细节！！！
直接这样写是会$tle$或$mle$的，所以考虑优化。
- 用滚动数组，再用哈希表来存储$mask$。导致的结果：$ac,4.2e5ms$
- 考虑$has_{x,y}$表示从$(x,y)$开始$m+2$个格子中哪些是白色的，然后如果当前放置的那个图案覆盖到的所有的都是黑色的，那么肯定不应该去更新这个状态。导致的结果：$2.9e5ms$
- 更改哈希表的哈希模数，以及增加一些$register$优化，导致的结果：$2.4e5ms$
暂时做不到更好了。
所以这告诉我们一些道理：
- 哈希表永远是状压$dp$的好朋友
- 调参永远是卡常的好朋友
- 多想一些小小的优化（比如这个$has$数组）永远是拿高分的保障
2019年3月3日
Codeforces 152 E
题意：给你一个$n\times m$的格子，每个格子里面有一个值$a_{i,j}$表示如果要将这个格子变成路的话需要花费这么多代价。现在有$k$个特殊格子$(x_1,y_1)..(x_k,y_k)$。求将这些格子联通的最小代价。
思路：看$k$这么小（$k\leq7$）肯定是状压$dp$。那么就要想状态是什么。
首先我们知道如果我们现在有两个特殊点的连通分量$mask0$和$mask1$，并且它们没有交集，如果我们想要将它们合并成同一个联通分量，我们需要找到一个连接点$P(x,y)$使得$mask0$和$mask1$都包含它，那么我们就可以不花费任何代价将这两个合并。但是这样不一定总是最优的。比如我们可能找到了一个点$P_0(x_1,y_1)$使得$mask0$包含它，而另一个点$P_1(x_2,y_2)$使得$mask1$包含它，将$P_0$和$P_1$通过它们的最短路连接起来，相当于加了一条边。这样也是一种转移的方式。
那么状态就是$dp(P,mask)$表示必须包含$P$这个点和$mask$中的特殊点的联通块需要花费的最小代价。转移如上所述。
然后考虑求答案的时候顺着$dp$的结果倒推到只有一个的情况，每次将$P_0$和$P_1$之间的最短路连起来就行辣。
Topcoder 10384
题意：给你一个森林，求是否能将这个森林的点集分成两部分，每部分放在一列中，要求边是直的并且不能交叉，问最少删哪几条边。
思路：我们考虑森林中的一棵树，以$u$为根，将$u$放在第一列。然后发现$u$的儿子们都应该放在第二列，并且如果我们不删掉$u$的这个儿子被放在了中间（即非最上和最下），它只有一种选择：将其所有的儿子到它的边删掉，将它们挪到其它地方。如果这个儿子在最上或最下，那么这个儿子可以取另一个可以有儿子的儿子，剩余的也必须没有儿子。
那么我们就有一个想法了。考虑$dp(u,i)$表示对于$u$这个节点，它可以取$i$个能取儿子的儿子，最少删边数。
我们考虑转移。对于$dp(u,0)$，我们不能有能够取儿子的儿子，那么对于每一个儿子，我们的做法是这样的：要么我们将$u$到这个儿子的边断掉，将这个儿子挪到别处；要么我们留下这条边，但是我们必须将这个儿子到它所有儿子的边删掉。
然后就会发现我们需要考虑对于一个节点$u$我们断掉它到它所有儿子的边的代价。对于第$i$个儿子就是$1+dp(son_i,2)$。我们记这个值为$val_i$。
然后考虑$dp(u,1)$。我们可以取$1$个能延伸其它儿子的儿子。枚举那个儿子$i$，那么$dp(u,1)$就是
$dp(u,0)-val_i+dp(son_i,1)$。
再考虑$dp(u,2)$，也是一样枚举那两个可以延伸儿子的儿子，$dp(u,2)$取
$dp(u,0)-val_i-val_j+dp(son_i,1)+dp(son_j,1)$。
其实这样少考虑了一种情况（就像我原先一样。
如果当前节点$u$取了$1$个儿子$i$，并且这个节点所挂子树是被孤立出去的，也就是说这个$i$是可以取两个延伸出去的儿子的，这可以让一些答案变少，比如我们断掉一个节点到它所有儿子的代价就会相应地变少。
那我们再来求这个取一个儿子的代价是什么。
首先肯定要将其它的儿子都断掉向它们的边，然后再取$dp(son_i,2)$就行了。
那么最后就是考虑怎么求方案了。
这个过程非常血腥暴力，是这样的：我们从头开始枚举每一条边，如果我们将这条边断掉之后再求一遍的答案也相应地减了$1$，就说明我们可以将这条边给断掉，由于要求字典序最小就将它加到答案中。
需要注意如果这条边可以被断掉那就真正断掉它。
2019年3月4日
Codeforces Round 1120
这场比赛做了$A$、$C$两题，排名$73$。
$A$题其实过的有点莫名其妙。。。就是我感觉好像能找到一个反例（现在发现我的算法是对的。。。
$C$题的心路历程：
- 第一眼：这不后缀自动机吗？？？
- 算了滚去写哈希表乱搞吧。。。
- 嗯怎么$mle$了？？？算了把数组改成$vector$吧。。。
- 嗯怎么又$wa$了？？？算了我还是老老实实去敲SAM吧。。。
- 嗯？？？$pretest\ passed$？？！！
所以就交了$3$次才过。。。
只是可惜了这场$unrated$
Codeforces 1120 A
题意：给$n$个数$a_1..a_n$，要从其中删去小于等于$n-m\times k$个数，使得将这个数组分成$k$个一段的序列时有至少一段满足以下条件：设这$k$个数为$c_1..c_k$，其中必须含有$b_1..b_s$这$s$个数（如果有重复得数量比$b$中的还多）。
问任意一种方案。
思路：我的思路比较鬼畜。。。
首先我们考虑满足要求的这$k$个数从$i$号位置开始后的情况。
首先我们需要看$b$中的每个数在$a$中出现的每一个位置，以便求出这个东西：
从$i$开始找$cnt_{b_j}$个$b_j$达到的最后一个$a_l$的最大下标$l$。
然后这玩意可以（明显的）通过维护现在到了对于所有的$j$，$b_j$的第几次出现来在$O(1)$时间内求出。
再判断一下将$i$之前的数删除到$i$保持在一个$k-$段的开头的代价加上将$k-$段中间的内容删除以至于满足的数们可以放在同一个$k-$段中的代价是否超过了$n-m\times k$。如果没超过就输出答案。
然后这个方案的输出折腾了我半天。。。我们应该将所有$i$之前的使得$i$不是$k$的开头的$j$都给他删掉，并且把$i$之后的不是$k-$段之内的也给删掉。
Codeforces 1120 C
题意：给一个串$S$，将这个串分成$t_1..t_m$，如果$t_i$在$t_1..t_{i-1}$中作为子串出现过，那么这个的代价是$b$，否则如果$|t_i|=1$，那么这个的代价是$a$。
问最少代价。
思路：第一次现场敲对$Suffix\ AutoMaton$祭
首先考虑$dp_i$表示处理到第$i$个位置，最少的代价。
然后向后枚举一个在$S_{1..i-1}$中出现过的子串$S_{i..j}$，转移$dp_{j+1}=dp_i+b$，或者$dp_{i+1}=dp_i+a$。
这个判断子串的过程有好几种方法：
- 用后缀自动机慢慢添加节点，然后直接按照上面的边跑看会不会
跑丢了跑到$null$那边去 - 做$lcp_{i,j}$表示从$i$和$j$开始的最长公共前缀，然后顺着这个转移。
- 把所有哈希值放到哈希表里面（这个莫名$wa$了。。。
- 直接暴力$string.find$。。。（能过！
- 。。。
其实我感觉$C$比$A$简单好多。。。
Codeforces 1120 A 分析
Markellonchik、chemthan、LHiC、Atreus、aid、yzyyylx、Barichek、nicklu0、stO、HwSh、teja349、Fekete、Rzepa、JustasK、Arturgo、huzzah：
使用$two\ pointers$来求出对于每一个$l$，最早的使$[l,r]$中包含$b_{1..s}$成立的$r$。
然后如果需要删掉的最少的数的个数满足要求，那么就输出方案。
mango_lassi、archie_fake、al13n：
对于每一个$i$，看$[i-(n-(m-1)*k)+1,i]$这一段区间（取能够取的最多的数）中每一个数有多少个，是否满足大于等于在$b$中出现次数的要求，如果满足那么就输出方案。用滑动窗口的办法来解决每一个数多少个的问题。
step_by_step：
和我的做法类似。
总结：大多数人都用的是$two\ pointers$？？？我还是太$naive$了啊，怎么也想不到。。。
Codeforces 1120 C 分析
V–gLaSsH0ldEr593–V、Radewoosh、prof.PVH、mitterr1999、chemthan、V–o_o–V、pavel.savchenkov、kmjp、bip_oqq：
首先通过$dp$算出$lcp_{i,j}=lcp_{i+1,j+1}+1$，然后根据$max\ lcp_{i, j}$来更新$dp_{i+k}$。
gskhirtladze、Benq、teja349、natsugiri、step_by_step：
通过$Z_Function$算出$lcp_{i,j}$。其余同上。
paulll：
通过$Suffix\ Array$算出$lcp_{i,j}$。其余同上。
Sooke、nicklu0、LHiC：
通过$Suffix\ AutoMaton$算出原串的一个前缀$S_{1..i}$中有哪些子串，用于判断之前是否出现过。
_Ash__：
通过KMP算出$lcp$。
Atreus：
首先求出一个前缀$S_{1..i}$中所有子串的哈希值，然后对于$i$二分出最长的是前面的子串的能转移到的$j$，然后转移。
总结：这题我明显$Over\ Kill$了啊。。。根本用不着后缀自动机的。。。
2019年3月5日
USACO 2019 Feburary Contest, Gold T1
题意：给定一棵树，每个点有点权，每次可以进行以下操作之一：
- 更改一个点的点权
- 求某条路径上的点的点权的亦或值
思路：这这这。。。金组什么时候第一题都是树链剖分了。。。
这题是个树链剖分的模板题。（但是我捣鼓了好久。。。
首先将原树进行树链剖分，将每一个节点分在一条重链内。然后链与链之间用轻链连接。
对于操作1，我们只用将这个点的值在$BIT$中修改即可。
对于操作2，我们这样处理：
首先我们假设$u$和$v$中$u$所在重链的头的深度大于$v$所在重链的头的深度。
那么我们从$u$跳到$u$所在重链的头时就不会忽略$u$和$v$的$lca$。
（这边很重要，我就是第一开始只考虑了$u$和$v$的深度比较，然后只过了样例，其它点一个没过。。。
将$u$跳到$u$所在重链的头的父亲，并且将答案加上[$u$所在重链的头，$u$]这段区间的亦或和。
然后迭代处理即可。
USACO 2019 Feburary Contest, Gold T2
题意：给一个$1..n$的排列，问这个排列的最长满足以下要求的前缀的长度：
如果我们按照顺序从第一个数遍历，每一个数有两种选择：
- 将这个数放在某个已有栈的栈顶
- 将这个数放在所有栈右侧新建的一个栈的栈顶
中间可以不限次拿走现存所有栈中最左的那个的栈顶的数。
然后要求是让每次拿走的数最终能按大小排序。
思路：首先肯定是二分最长前缀辣
$check$的时候是这样做的：
每次找到栈顶比当前取的数大的第一个栈，把当前的数压到栈顶里，因此可以证明栈顶大小从左向右单调上升。
然后中途看最左栈顶是不是当前没拿到的最小数，如果是则将它弹掉。
然后就好辣（这题比第一题简单好多好多。。。
USACO 2019 Feburary Contest, Gold T3
题意：给$n$个矩形，可以再画两个互不相交的，求最大的被$k$个矩形覆盖的面积。
思路：（这题意怎么这么简单。。。
首先我们通过差分算出每一个点被多少个矩形覆盖了，然后每一个新画的矩形所能做出的最大贡献就是它覆盖的面积中被$k-1$个覆盖的$-$被$k$个覆盖的。所以我们可以通过$dp$预处理出$[[0,200],[0,200]]$的一个删掉上面$i$行的子矩形中新画一个所能构成的最好情况，同理算出删掉左边$j$列的最好情况，枚举第一个矩形，然后第二个矩形所能造成的贡献都预处理好了，直接用即可。
Codeforces 204 E
题意：给$n$个串，求对于每一个串在至少$k$个串中出现的它的子串$S_{l..r}$有多少个。
思路：后缀自动机上$dp$。。。
我们首先构造出这$n$个串的后缀自动机，其中需要注意将某个串的构建完了后直接将$lst$指针赋为$root$，那么就可以包含这些串的所有子串并且不会有问题。
然后我们就考虑如何来算出某一个子串在$n$个串中出现了多少次。
假设现在我们从$S_i$的开头走到第$j$位，走到了节点$u$，那么
看从$u$开始，沿着$link$一直走到$root$的一堆节点$v_1..v_k$，这些节点表示的最长后缀没有在$S_i$中出现过，那么它们现在就标记为在$S_i$中出现过了，然后这些节点代表了结尾为$j$的所有子串们（根据定义），所以没有漏掉任何一个子串。
下面就是要求每一个节点对$S_i$的贡献了。对于节点$u$，它对任何一个串的贡献就是它的$link$的贡献加上如果它出现大于等于$k$次，那么就再加上这个节点表示的子串数量：$len_u-len_{link_u}$（这个非常重要）。
那么顺着$S_i$跑到的每个节点$u$统计下答案就可以辣
Codeforces 912 E
题意：给$n\leq16$个素数$p_1..p_n$，求第$k$个所有质因数都在$n$个数中的数。
思路：折半搜索。。。我原来胡搞毛搞怎么也搞不动$16$的点。。。直到我突然想到了分成两个$8$来搞。。。
首先我们发现$n\leq8$的我们二分+搜索就可以很简单地解决，那么我们据此来搞搞$n\leq16$的点。
我们将这些素数分成$p_1..p_{\lfloor n/2\rfloor}$、$p_{\lfloor n/2\rfloor+1}..p_n$两部分，那么我们可以先将满足这两部分要求的所有小于等于$10^{18}$的数都搜出来。
然后二分答案。$check$的时候利用$two\ pointers$来求满足两部分之一的数们。
这题搞了好长时间。。。太坑了。。。
2019年3月6日
Codeforces Round 1132
这场比赛做了$A$、$B$、$C$、$F$四题，排名$89$。
$A$题$wa$了一次，少考虑了一种情况
$D$题最后做出来，但被$hack$了。。。被$hack$的原因是没有想到答案会超过$10^{12}$（毕竟这个时间上的优化也是在最后迫不得已的情况下加的，就没有考虑正确性。。。
Codeforces 1132 C
题意：给一些区间$[l_i,r_i]$，从中删掉两个，求剩下的区间最多能够覆盖的格子数量。
思路：首先枚举第一个删掉的区间，然后我们可以通过差分来求出每个格子被多少个区间覆盖了，随后求出所有格子中被$1$个区间覆盖的数量的前缀和，再枚举第二个删掉的区间，找删掉的$1$个区间覆盖的最少的即为答案。
Codeforces 1132 D
题意：给$n$个电脑的电量和耗电速度，你可以买一个充电器，它的充电速度是每秒$v$单位，$v$你自己定。问最小的$v$能使得在$k$秒内每秒给某电脑充电，没有电脑的电量小于$0$。
思路：首先二分$v$，然后$check$的时候是这样的：
维护每一个电脑没电的时间，每次将最早没电的那个给充电一秒，如果最早没电的那个在充点前已经没电了，那么就肯定完蛋，否则一直跑到第$k$秒看是否能跑完。
Codeforces 1132 E
题意：给$cnt_i$个$i$（$1\leq i\leq 8$），问用这些数所能构成的最大的不超过$W$的数。
思路：随机+贪心。。。
我们考虑将贪心和一个奇奇怪怪的随机算法结合在一起取最大值。
贪心：我们枚举所有的$8$个数的排列，然后将第$i$个数尽量取到能取的最大值，加入答案。
随机：首先我们考虑约束条件$t$。$t$从$1$开始，然后逐步收敛为$t\times0.999999$，$t\times0.999999^2$、。。。
然后我们随机地考虑一个数$i$，再看如果当前的数超过了$w$，那么我们肯定要将$i$取的个数压下去，则随机$[0,nowchosen_i\times t]$中的一个作为新的$i$取的个数。否则我们需要将$i$取的个数加上去，则随机$nowchosen_i+[0,(cnt_i-nowchosen_i)\times t]$中的一个作为新的$i$取的个数。
最后取这两种方法的$max$即可。
Codeforces 1132 F
题意：给一个串$S$，问每次删除连续的一段相同字母，最少删几次将原串删空。
思路：考虑区间$dp$，我们看要删多少次能把$[l,r]$删空，那么最终答案就是$dp[0,n]$。
那么就枚举最后一次删除的字符是$c$。
由于我们可能有$ababa$这种情形，不一定只是$c-$段间隔起来的区间们需要被单独处理，而是可能是连续的几段，头尾是$c-$段即可。
那么就需要另一个$dp$。设$f(i)$表示到了第几个$?-$段，然后转移到$f(i+j)$，需要在值上加上$dp[i+1,i+j-1]$。
然后用$f(r)$更新$dp[l,r]$就好辣
Codeforces 1132 C 分析
tataky：
首先我们将所有的互不包含的区间们放在$v$里，然后看被包含的区间有多少，如果超过2个就直接输出答案，否则需要通过$dp$来求：
首先我们考虑$dp$的状态。那么首先我们需要记录删掉了多少个区间$(0..2)$，还要看现在已经到了第几个按顺序排列的区间，并且如果删除的是连续的两个区间，还要存前一个没被删掉的区间在当前的区间前面多少个。
所以$dp(i,j,k)$表示现在到了第$i$个区间，然后已经干掉了$j$个区间，现在连续地删掉了$k$个区间，最多可以覆盖的格子个数。
考虑转移。我们考虑第$i$个区间是否被删掉，如果删掉，那么转移到$dp(i+1,j+1,k+1)$，否则转移到$dp(i+1,j,0)$。
V–gLaSsH0ldEr593–V、neal、kmjp：
和我的思路差不多，是首先用差分求每一个格子被多少个区间覆盖了，然后考虑枚举第一个删除的区间，看将它删去之后所覆盖只被一个区间覆盖的格子数量最少的区间，这就是第二个区间。只需要处理一下被一个区间覆盖的格子数量的前缀和就可以了。
2019年3月7日
SPOJ GSS1
题意：给一个序列以及一些询问，每个是问$[l,r]$中最大连续子序列和是多少。
思路：这个问题是以下问题的基础。
我们考虑用线段树来解决这个问题。
首先我们来想想如果要求出最大连续子序列和需要什么信息。
对于$[l,m)$和$[m,r)$这两个区间，我们需要将它们合并成$[l,r)$这个区间。
那么我们考虑分治地来解决这个问题。把问题分成三部分：
- $[l,m)$中的最大子序列和
- $[m,r)$中的最大子序列和
- 左端点在$[l,m)$内，右端点在$[m,r)$内的最大子序列和。
其中前两个部分可以递归处理，而第$3$个部分则需要记录$[l,m)$的最大后缀和以及$[m,r)$的最大前缀和，以便求出此部分的值。所以对每个节点维护$[l,r)$的和、最大子序列和、最大前缀和、最大后缀和。
将值上推的时候这样做：
- 首先将$[l,r)$的和设为$[l,m)$的和加上$[m,r)$的和。
然后考虑最大前缀和（最大后缀和与之对称，略）：这个最大前缀和的结尾可能有两种情况：
- 在$[l,m)$中，即$[l,m)$的最大前缀和
- 在$[m,r)$中，即$[l,m)$的和加上$[m,r)$的最大前缀和
然后最大子序列和就是$[l,m)$的最大后缀和加上$[m,r)$的最大前缀和。
然后就好辣。
SPOJ GSS3
题意：给一个序列以及一些询问，每个是$1)$将$x$这一位上的数改成$v$；$2)$问$[l,r]$中最大连续子序列和是多少。
思路：这题比GSS1只是多了修改操作，而这只是单点修改，所以直接加上正常线段树的$update$操作即可。
SPOJ GSS5
题意：给一个序列以及一些询问，每个是问$max\ \sum_{k=i}^ja_k(x_1\leq i\leq y_1,x_2\leq j\leq y_2,x_1\leq x_2,y_1\leq y_2)$。
思路：我们将$y_1$和$x_2$的大小情况分两类考虑：
- $y_1<x_2$时，这两个区间没有任何交叉，所以答案肯定是$[x_1,y_1]$的最大后缀和加上$[y_1+1,x_2-1]$的和加上$[x_2,y_2]$的最大前缀和。
- $y_1\geq x_2$时，这两个区间的交叉是$[x_2,y_1]$这段，那么我们要分几种情况考虑：
- $i$在$[x_1,x_2-1]$里，$j$在$[x_2,y_1]$里：$[x_1,x_2-1]$的最大后缀和加上$[x_2,y_1]$的最大前缀和。
- $i$在$[x_1,x_2-1]$里，$j$在$[y_1+1,y_2]$里：$[x_1,x_2-1]$的最大后缀和加上$[x_2,y_1]$的和加上$[y_1+1,y_2]$的最大前缀和。
- $i$在$[x_2,y_1]$里，$j$在$[i,y_1]$里：$[x_2,y_1]$的最大连续子序列和。
- $i$在$[x_2,y_1]$里，$j$在$[y_1+1,y_2]$里：$[x_2,y_1]$的最大后缀和加上$[y_1+1,y_2]$的最大前缀和。
- 然后取$max$就好辣。
SPOJ GSS7
题意：给一棵树以及一些询问，每个是$1)$将$a\rightarrow b$的路径上每一个点都赋成$c$；$2)$问$a\rightarrow b$的路径上每一个点组成的序列的最大连续子序列和。
思路：树链剖分都出来了。。。
先看第一个询问。
这个询问还是比较普通的。。。
套个树链剖分的模板做一下就行了，不过线段树中还要加上区间修改的操作。其实也蛮简单的：）
然后我们考虑第二个询问。
首先这个不可以套模板了。。。
最大连续子序列和不是个可以分段搞的东西。。。
然后放弃想了想发现我们可以$O(log^2)$地做！！！
首先我们按照正常步骤来把这条路径上所有的重链作为一个个区间，记为$A_{1..m}$。
然后我们根据（da）树链剖分（le）复杂度（ge）的证明（biao）发现$m$不会超过$O(log\ n)$。
所以开心地暴力。。。
枚举区间开头$l$，区间结尾$r$，那么就是$\sum_{i=l+1}^{r-1}A_i$的和加上$A_l$的最大后缀和加上$A_r$的最大前缀和。
还有一种情况就是答案就在$A_i$中，即$A_i$的最大连续子序列和。
搞死我了。。。写了$5K$。。。
2019年3月8日
SPOJ GSS6
题意：给一个序列，有以下询问类型：
- $I\ x\ v$：在第$x-1$位和第$x$位之间插入$v$
- $D\ x$：删除第$x$位
- $R\ x\ v$：把第$x$位替换成$v$
- $Q\ x\ y$：求$max_{x\leq i\leq j\leq y}\sum_{k=i}^ja_k$。
思路：由于有插入删除我们不能用线段树了，那么就用$FHQ\ Treap$吧。
首先我们在$treap$的每个节点中存储的信息应该和GSS1中线段树的每个节点存储的信息差不多：
这个节点所代表的区间的最大前缀和、最大后缀和、最大连续子序列和、和，以及这个节点的值。
然后只需要实现$pushup$操作在$split$和$merge$的时候将节点两个儿子的信息推到上面去就可以了。
有个坑：它的数据中行末有空格！！！所以$getchar$并不怎么好使。。。
我第一开始竟然忘了$pushup$这个节点代表的区间的和。。。
所以其实这题比GSS7简单多了。。。
2019年3月9日
Codeforces Round 1137
这场比赛做了$A$、$B$，排名$376$。
主要是$A$题做的时间又长又交了两次$wa4$的。
这两次错误的提交是因为我第一开始想的求最大值很不对，竟然还有$min$在里面。。。
Codeforces 1137 A
题意：给一个矩阵，问对于每一个格子$(x,y)$，把第$x$行和第$y$列的值取出，要求将它们每一个赋上一个正整数，要求同一行、列中大小关系依然相同，问最大的数。
思路：我们先考虑每一行（列）的数们把它们赋成一个个正整数，然后发现就是求这个行（列）中有多少个互不相同的数，所以将每一行（列）的数排序去重，再来考虑把行列结合的问题。
然后我们发现在结合行列的时候我们应该看这一行、列中此数是第几个，记为$C_x,C_y$。然后记这一行、列各有多少个不同的数，记为$S_x,S_y$。然后我们可以发现我们的$(x,y)$这个数必须赋成$max(C_x,C_y)$这个数，要不然如果赋了$min(C_x,C_y)$就会发生$max(C_x,C_y)$所对应行（列）的最小值小于等于$0$的情况。
所以假设$C_x>C_y$，如果不是就$swap$一下。
然后考虑答案。我们只用以$max(S_x,S_y+C_x-C_y)$作为答案即可。就是考虑行和列的最大值，对于列来说我们将原来的$C_y$改为现在的$C_x$，那么最大的就会加上一个$C_x-C_y$。
Codeforces 1137 B
题意：给两个串$S$、$T$，问将$S$中字符任意调换后出现$T$次数最多的方案。
思路：我们首先考虑怎么样放$T$才是最优的。我们直观上考虑前后两个$T$的出现肯定要重叠一定的面积，那么我们考虑$T$的最长的与前缀相同的后缀$T’$，我们最终的答案希望是这样的：$TT…TT’$。
所以我们枚举$T’$出现的次数，看$S$中字符是不是够即可。$T’$的长度需要用$Z_function$或KMP来求。我考试的时候忘了KMP怎么写，于是就用$Z_Function$代替。掌握不熟练。
NOIP2017 D1T3 逛公园
题意：给一个有向图，每条边有权值，问从$1$到$N$的长度不超过最短路长度$+K$的路径条数。如果有无数条则输出$-1$。
思路：我们首先扔掉$-1$的情况，再扔掉$K>0$的情况，来考虑最裸的最短路计数。那么我们就可以考虑$dp(i)$表示走到$i$号节点有多少种路径。那么一个记忆化搜索就可以完成这个操作辣。这玩意能得$30pts$。
然后考虑$K>0$的情况。那么$dp$的维度就不能只是$1$维了，需要加上一维$dp(i,j)$表示到了$i$节点，距离为$dis_i+j$的路径条数。然后转移的时候枚举$v\rightarrow i$，从$dp(v,dis_i+j-cost_{v,i}-dis_v)$转移来、用记忆化搜索即可。这玩意能得$70pts$。
最后我们考虑有$-1$的情况，样例告诉我们：有$-1$必定有$0$环，但有$0$环不一定有$-1$。所以我们来找找如何在记忆化搜索中找到$0$环。
不特别特别难发现：如果我们现在有一个正在查询的状态$dp(i,j)$，而我们现在又看到了我们需要查询$dp(i,j)$，那么我们肯定这边有一个权值和为$0$的环。
证明：
我们证如果没有权值和为$0$的环，那么不会出现上述情况。
首先如果根本就没有环，那么肯定没有任何问题，根本就不会回到$i$这个点。
如果有权值和非$0$的环，那么转了一圈会回到$dp(i,j’)(j’<j)$，因为每次我们加上$dis_i$减去$dis_v$的过程经过一个环全消掉了，不会对$j$产生影响；而每次$+j-cost$，会给$j$减去$\sum cost$，所以$j$只会变小。
证毕。
所以这样就可以$ac$辣。
2019年3月10日
NOIP2017 D1T3 逛公园 分析
把这些程序分成以下几种类型：
- ZJ-0164、ZJ-0389、GD-0090：
首先我们跑一遍$dijkstra$或者$spfa$求出从起点开始的最短路径$dis_i$，
然后考虑用记忆化搜索转移$dp$：$dp(i,j)$表示到了$i$节点，到当前节点的距离是$dis_i+j$的路径条数。
然后枚举$v\rightarrow i$，从$dp(v,dis_i+j-cost_{v,i}-dis_v)$转移即可。 - ZJ-0188、ZJ-0542、ZJ-0571：
首先在反向图中从终点跑一遍$dijkstra$，求每个点到终点的最短距离，记为$dis_i^0$；
再在原图中跑一遍，求每个点到起点的距离，记为$dis_i^1$。
然后我们就可以对所有$0$边进行强连通分解，
看是否有一个$0$环使得一条经过这个$0$环的最短路径的长度小于等于$dis_n^1+k$的，
如果有那么肯定有无穷解，否则肯定有有限解。
那么再用记忆化搜索转移$dp$即可。$dp$状态同上。
（ZJ-0542的做法与之类似，但不完全相同，比如他把所有的节点各拆成$k$个来进行$dp$、没有直接把无穷解给输出等）
（ZJ-0571的做法也与之相似，但也不完全相同，比如他就在$dp$中途判断$-1$的情况） - ZJ-0274、ZJ-0221、ZJ-0508、ZJ-0417、GD-0112、GD-0349：
首先在反向图中从终点跑一遍$dijkstra$，求每个点到终点的最短距离，记为$dis_i^0$，
然后用它来求出每一个点是否在最短路树中，这个概念就是如果$i\rightarrow v$且$dis_i+cost_{i,v}=dis_v$，那么$i\rightarrow v$就在最短路树中。
同时我们还需要记录每一个节点是否能够从$n$走到，如果不能那么这个节点也没有必要被存下来，因为它不可能对答案造成任何贡献
然后呢我们可以将每条边$i\rightarrow v$的边权改成$dis_i^0+cost_{i,v}-dis_v^0$，这个记录的是如果我们从$i$走到$v$把最短路的长度增加了多少，然后再对新图跑$dijkstra$，记为$dis_i^1$用来拓扑排序：但这里的“拓扑”序只是对于最短路树而言的，因为最短路树肯定是一个$dag$。拓扑排序完了之后如果没有把所有的有可能有贡献的节点都放进去，那么就肯定有无穷解。
最后考虑$dp$：$dp(i,j,k)$表示到$i$节点，到当前节点的距离比最短路多的值是$j$，走的最后一条路是不是属于最短路树中的，路径条数。那么转移是枚举$v\rightarrow i$，从$dp(v,j-cost_{i,v}^{now},v\rightarrow i$是不是属于最短路树$)$转移来。
求答案的时候就是枚举最后一个走树边到达的节点$i$，剩余走最短路，加上$dp(i,j,0)$。
其实第三维也是可以不加的，只要你最后求答案的时候只把$dp(n,i)$加入答案中即可。（比如ZJ-0221）
（GD-0349虽然进行了拓扑排序，但是根本没有用，只是用来判断无穷解，$dp$的时候还是用的记忆化）
2019年3月11日
SPOJ GSS4
题意：给一个序列，有以下几种询问：
- 将$[l,r]$的所有数都改成它们的正平方根
- 求$[l,r]$的和
思路：首先我们看求平方根的特性。
最大从$10^{18}$开始，到$10^9$，$31622$，$177$，$13$，$3$，$1$。所以我们知道将每一个数一直取平方根能取的次数是常数级的，到$1$之后就会出现循环，那么我们只用维护一个$set$来存储所有的非$1$的数，每次询问的时候如下处理：
- 对于修改操作，我们只需要在$set$中找到所有的在$[l,r]$这个区间中的数，把他们变成自己的平方根，在$bit$中区间修改一下即可。如果中间有某个数变成了$1$，那么我们就将其从$set$中删去。
- 对于查询操作，只需要在$bit$中查询和即可。
所以这题这样一分析就一点都不难了。
Codeforces 1137 C
题意：给一个有向图，一周有$d$天，每一个点在每一周的某些时刻会开放，现在可以在这个图上从$1$号点开始随意地走，问最多能走到多少个开放的点。一个点如果重复走到了很多次，只算一次。
思路：这空间太难卡了。。。
我们首先考虑将这个图的所有点都拆成$d$个，变成$n\times d$个点（为下文卡空间埋下伏笔），
即将$i$变成$(i,j)$，其中$j$表示到$i$的时候是一周的第$j$天（这里天数是$0-start$，即一周的第一天是$j=0$）
然后将每一条边$u\rightarrow v$都变成$(u,i)\rightarrow(v,(i+1)\ mod\ d)$，那么我们就会发现我们要求的就是$(0,0)$开始我们最多能跑到多少不同的$(i,\star)$。
所以我们将这个新图强连通分解，对于每一个强连通分量求出这个连通分量中不同的原来点的个数。
为了避免重复计算，我们证明以下结论：
在新图的一条链中出现的所有相同原图节点的节点们必定在同一个新图的强连通分量内。
证明：
首先我们假设这条链中有两个节点$(u,i)$和$(u,j)$，那么原图上肯定有一个包含$u$的环，其长度$mod\ d$为$j-i$，那我们从$(u,j)$再走$d-1$次这个环，肯定回到$(u,i)$。所以它们两个节点肯定在一个强连通分量内。证毕。
然后我们考虑$dp(i)$表示现在走到了第$i$个强连通分量，最多能够走到的点的个数。
那么转移就是枚举$i\rightarrow j$，从$dp(j)$转移。
但是，只是这样的话肯定会$mle$，我们需要卡空间。
我的做法是把所有的关于$stl$、递归的东西统统变成手写的，然后就变成了一堆奇奇怪怪的东西：
邻接表我用的是$vector$，那么不要了！变成前向星！
强连通分解我用的是$kosaraju$，那么这两个$dfs$都不要了！变成手写的递归！
$dp$的时候我用的是记忆化搜索，那么这个$dfs$也不要了！变成拓扑排序后$bfs$！（但是最后还是变成了手写递归-_-
关于手写递归：
首先我们要知道白点、灰点、黑点这三个概念：白点是没有访问过的点，灰点是正在访问的点，黑点是已经访问过了的点。它们分别对应了$vis$中的$0$、$1$、$2$。
然后我们手动维护一个调用栈$stk$，那么我们的$dfs$应该是这样的：
1 | // 起始点: s |
十分不优美，但为了卡空间也没什么办法。。。
$stk$千万不要用$std::stack$，肯定会$tle$。。。
老老实实手写，如果感觉空间不够也不要用$vector$。大胆开不要怂小心地算一个上界开大一点点的（比如加一个微不足道的常数$10^5$）
SPOJ GSS 2
题意：给定一个序列，每次询问区间内最大去重子段和。
思路：这题比第一题就多了几个字，但是难度确是天上地下。。。
首先这个肯定是在线做不来的，那么考虑离线处理。
那么我们看如果我们将区间的右端点$R$右移一位之后会发生什么。
假设$a_R$最后一次出现是$b_{a_R}$，那么我们考虑从$1$到$R$每一个点开始一直到$R$的这个子段的和的变化。
首先$b_{A_R}$及其前肯定不会有任何变化，那么只是$b_{a_R}+1$到$R$的区间内会加上$a_R$。
为了处理$i$到$i..R$的最大子段和，那么我们需要对于每一个点记录历史最大值。
所以考虑线段树。每一个节点$i$代表的区间是$[lb_i,rb_i)$，中点为$md_i$，对$i$存储以下信息：
- $[lb_i,rb_i)$的最大值和历史最大值
- $[lb_i,rb_i)$的增加值和历史最大增加值
然后我的思路就到这里了。。。我怎么搞都搞不对下推操作。。。然后看了魏铭神仙的题解发现下推应该这么做：
以$[lb_i,rb_i)$下推到$[lb_i,md_i)$为例，下推到$[md_i,rb_i)$同理。
首先我们考虑怎么用$[lb_i,rb_i)$的历史最大增加值去改变$[lb_i,md_i)$的历史最大值。
首先确定$[lb_i,rb_i)$的历史最大增加值是相对于上一次下推而言的，并不是全局历史最大。
那么$[lb_i,md_i)$的历史最大值就肯定需要和$[lb_i,md_i)$现在的最大值$+[lb_i,rb_i)$的历史最大增加值取一个$max$。
下面考虑$[lb_i,md_i)$的历史最大增加值和$[lb_i,rb_i)$的历史最大增加值的关系。
首先我们知道现在$[lb_i,md_i)$增加多少，并且这个值在”历史”的范围内是没有改变过的（要不然肯定下推了），所以我们应该将$[lb_i,md_i)$的历史最大增加值和$[lb_i,rb_i)$的历史最大增加值$+[lb_i,md_i)$的增加值取个$max$。
$[lb_i,md_i)$的增加值和最大值和正常的线段树相同，略。
下面来想上推操作。这就比较简单了，只是将两个儿子的最大值推到当前的最大值上，当前的历史最大值和最大值再取一个$max$即可。
好难啊。。。
2019年3月12日
SPOJ GSS6
思路：按照魏铭的方法写的。他竟然用了$Splay$。。。写疯掉了，$splay$和$rotate$两个函数已经忘的差不多了，想了半天。。。然后其中如果要查询一个区间就把区间的右端点后一个和左端点分别splay到根和根的左节点，那么根的左节点的右子树就是需要查询的区间。比Treap不知道难搞了多少。。。
SPOJ GSS7
思路：按照魏铭的方法写的。他在求答案的时候写得非常自然，用了线段树中写的$pushup$函数，将整个长链变成了一个节点，左右两个节点再合并一下变成一个。这样写的既比我的方便又自然。
Codeforces 848 C
题意：给$n$个数，$m$个询问，每一个询问有以下类型：
1 p x：将第p位改成x。2 l r：求出$[l,r]$区间中每一个出现的数的最后一次出现位置-第一次出现位置的和。
思路：我比较愚钝，只会最菜的$O(n\times sqrt(n)\times log(n))$的做法。
首先我们来想查询操作。我们将原序列分成B个一段，其中B是自己指定的。然后我们维护好所有的从第$i\times B$个到第$j\times B-1$个的数中的答案，然后把第$l$个到第$i\times B-1$个，第$j\times B$到第$r$个的数都重新计算位置，就求出了答案。
下面来搞超难弄的修改操作。我们把修改操作拆成先删除p位置的数，再将x插入到第p位中。
首先看删除。我们肯定要维护每一个数都在那些位置里面出现了。那么我们就设这个数在p之前的一次出现在prv位，后一次出现在nxt位。
然后我们看会有那些块的区间受到了影响。
首先我们看以0到prv之间为开始，now到nxt为结束的段，它们原来的答案是now-某个数，但现在变成了prv-某个数，所以减去了now-prv。
再看以prv到now之间为开始，nxt到n为结束的段，它们原来的答案是某个数-now，现在变成了某个数-nxt，减去了nxt-now。
所以就知道我们需要的是区间修改、单点查询的数据结构$–bit$。
然后就考虑添加。其实添加的操作和删除是正好反过来的，只用加上原来减去的数就可以了。
然后只是这么做是会WA在样例上的，因为我们没有特判如果没有nxt或者prv的情况。。。特判一下即可。。。
但是还是会TLE哒，我就T了好长好长时间。。。然后我调参，卡常。。。搞了半天才好不容易擦着时限过了。。。
2019年3月13日
Codeforces 848 C 分析
V–o_o–V：
首先我们考虑每隔一段时间把现在更新的所有内容集体更新一下。
然后因为每O(sqrt(N))次查询就更新不会使当前剩余没有更新的数太多，并且也不会更新太多次，所以就这样做。
集体更新的时候我们维护一个vals数组表示每一个数出现多少次，然后还有一个nvals表示没有被更新进去的数出现了多少次。
我们更新的时候只关注从当前开始下sqrt(N)次查询。
然后我们通过分块来求出所有的下sqrt(N)次查询的最大值和最小值：
对于最大值，我们从左向右扫描，不断加入新的数，设当前的数为a[i]，上一次出现是在p[a[i]]，那么我们原来说在p[a[i]]处a[i]最后一次出现，但现在需要将那一次出现删除，在i处增加一次出现位置。对于以i结尾的询问们，就可以通过分块处理的动态前缀和来求出这一个区间内最后一次出现的数的位置和。
对于最小值也是一样，不过从右向左扫描即可。
对于修改操作，我们只需要将当前修改的数通过插入排序放到一个chg序列里面即可。
对于查询操作，我们首先取更新时算出的最大出现和最小出现和，然后把至当前为止新加的更新都通过nvals来算出它们第一次出现位置和最后一次出现位置的差。
优化过程：
TLE6 -> TLE6：调了个sqrt(N)的参数（250 -> 317，然而并没有太大的用处），把cin改成了scanf（。。。）
TLE6 -> TLE7：增加了一些小的优化，比如将chg改成了数组（原来用的是vector），把vals改成了vector（原来是set）等。
TLE7 -> TLE7：这是一次测试用提交，他怕自己是因为O(log n)求某个数在[l,r]区间中的最早最晚出现的差的操作次数太多而超时的（但是他其实是每次重算nvals花了太多时间）
TLE7 -> AC：将树状数组改成了分块，并且将每次更新的时候重算的nvals改成了每一次查询就更改需要改的数（这个才是重点）
Reyna：
首先我们把所有的询问分成每sq个一组进行处理，其中sq为sqrt(N)
然后我们考虑从bg到ed的sq个询问怎么处理。这里其实和V–o__o–V的差不多，只是他没有分别求出每一个查询的区间中的每一个数出现的最早和最晚位置，而是直接用树状数组求出了所有数从第i位开始出现的最早位置-第一次出现位置的和。
然后也是从左向右扫描，不断加入新的数，然后对于查询(ql,qr)只需要求出sum(qr)-sum(ql-1)即可，因为最晚-最早是可以相减的：假设我们现在考虑x这个数，在[1,qr]中最后一次出现为i（因为是从左向右），在[ql,n]中第一次出现为j，[1,ql]中第一次出现为k，那么[ql,qr]的答案就是(i-k)-(j-k)=i-j。
最后再将这sq个中间的新加的更新都放到marked里面，暴力将这些都算出来加进答案中。
TimonKnigge：
树。。。树套树。。。
首先弄一棵zkw线段树，在每一个节点上是一棵Treap，其中存的内容是这一个区间内所有数最后一次出现-第一次出现的和。
我们考虑修改操作。首先我们需要将当前的这个数删掉再添加。
删除的时候就是我们把当前这个数的前后找出，记为pre和nxt，那么我们需要将原来这个数的在这个地方的出现删去，将这个数后一次出现的答案改成nxt-pre。
添加的时候也是差不多，把nxt的答案改成nxt-now，把now的答案改成now-pre即可。
那么查询的时候就是在线段树中找到需要查询的节点，把其中的>=l的部分都计入答案中即可。
SkyDec：
好像叫什么CDQ分治？？？
首先我们把所有的修改、查询询问按照时间排序，其中每一个修改操作都要变成删除（把nxt的答案改成nxt-pre）+添加（把now的答案改成now-pre，nxt的答案改成nxt-now），然后考虑前一半、后一半时间的修改对查询的影响，把他们合并，就是按照每一个操作的右端点排序，然后用bit维护每一个位置所对应的后缀中所有最后一次出现的数减去第一次出现的数的位置的和，然后按照右端点顺序从左向右扫描，对每一个求答案即可。
2019年3月16日
ZOJ 3463
题意：有一个钢琴，一个人把左手放在L位置上，右手放在R位置上，要弹某$n$个键，每个手最多能够得着9个位置，并且两只手不能交叉。把手移动的代价是大拇指移动的距离的平方根。问弹完这么多键之后最少花的代价。
思路：肯定是dp啊。考虑$dp(i,j,k)$表示当前要弹第i个键，左手大拇指在j位置，右手大拇指在k位置，最少代价。
然后转移的时候肯定只会移动一只手。那么从J移动到j’，从i移动到i’都要被算到。
并且还要判断两只手是否会重叠，我数数都能数错。。。连wa两次。。。真是。。。
Codeforces 710 F
思路：KMP学的还是不过关啊。。。
按照字符串的长度分类，如果长度大于$\sqrt{n}$的就扔到什么地方等待查询，否则就扔进trie里面。
对于查询，我们先在trie树中暴力找有多少出现过的子串，因为trie中长度不超过$\sqrt{n}$，那么这个操作总共不会超过$n\sqrt{n}$次。
然后对于每一个长度大于$\sqrt{n}$的，把kmp的fail数组构造出来，暴力在待查询串中查询出现次数。因为长度大于$\sqrt{n}$的不会超过$\sqrt{n}$个，所以这个的总次数也不会超过$n\sqrt{n}$。
但是我的kmp学的不好，写错了好多好多次。。。（我太菜了.jpg
还是要多打打板子啊。。。
2019年3月18日
UVA 11404
我用了最暴力的做法：考虑$dp[i][j]$表示$S[i..j]$的最长回文子序列的长度以及字典序最小的那个。
然后转移的时候如下处理：首先$dp[i][j]$要取$dp[i+1][j]$和$dp[i][j-1]$的最大值（因为可以两端中有一个不取），
然后如果$S[i]=S[j]$，那么我们就可以从$dp[i+1][j-1]+2$转移过来，并且字符串也需要更新。
然后比较字典序的时候就直接暴力按位比较。
最后只要注意一下多测把所有dp值都要赋初值。（就因为这个我吃了好多次亏（虽然不是这题
ZOJ 3200
首先我写了个高斯消元，但是消出来了一些奇怪的东西，我就放弃了。。。
然后只好考虑dp：$dp[i][j][k]$表示走到了第i步，到了$(j,k)$这个节点的概率。
那么答案就是边上节点在所有的步数走到的概率加起来第一次超过$p%$的地方。
然后转移的时候枚举现在要走到哪一个方向，走到$(j’,k’)$，就可以转移到$dp[i+1][j’][k’]$。
然后一共需要走的步数是看对于当前这一步所有的节点所能到达的概率是不是都是0（为了浮点误差，我们需要把=0改成小于EPS）
如果全等于0，那么下一步也没有去转移的必要了。
最后把所有的边上的答案加起来。为了不爆空间，滚动数组，只把边上的和记录下来即可。
还为了不tle，循环展开，直接转移到$(j+1,k)(j-1,k)(j,k+1)(j,k-1)$即可。
POJ 1179
题意：给一个多边形（烟雾弹$\times1$），每一条边上有一个运算符号$+$或$\times$，求割掉一条边后（烟雾弹$\times2$）可以通过适当的操作顺序（烟雾弹$\times3$）来达到最大的最终节点的权值（烟雾弹$\times4$），操作如下：
每次选一条边（烟雾弹$\times5$），然后把这条边现在连接的两个节点合并成他们节点的权值之积（或和）。
思路：把这个题意改一下就是：给一个$2\times n$的序列，两个数之间会有符号，前n个数之间的符号对应等于后n个数之间的符号，然后求其中每一个长度为$n$的区间做以下操作之后可以得到的最大值：
枚举一条把原序列切成两部分的“边”，然后看这两部分取到什么值，然后乘起来或者加起来成为现在这个序列的值。那么这肯定可以用区间dp来解决。就考虑$f^{min}{i,j}$和$f^{max}{i,j}$表示$i..j$这一段中，最小的和最大的能够表示出来的数是什么。之所以要最小的是因为我们有乘法操作，如果我们弄出了两个非常小的负数，那么他们的乘积是非常大的。然后转移的时候就枚举那条边就好了。
然后为什么要倍长中线这个序列呢？因为我们需要求的是一个烟雾弹多边形，就要循环处理。
2019年3月19日
POJ 3476
首先写了个treap，然后常数太大tle了。。。
然后想了个极为复杂的方法，是一共7个dsu，3个bit，还有一个set。然后写了一半就歇菜了。。。
然后看dxm的方法，是这样做的：
首先我们用三个并查集分别维护以下信息：每一个位置左边第一个没被删掉的，右边第一个没被删掉的，它所在的相同字符子串的第一个位置。
然后我们还需要维护所有的相同字符子串的起始位置和长度，放在一个优先队列里面，为了取最大值。
然后还要存从第i位开始的那个相同字符子串的长度。
那么我们每次从优先队列中取出最大的那个子串，然后不断地沿着右边第一个没被删掉的往后跑，删掉途中所有的，
然后看当前删掉的相同字符子串的右边一个相同字符子串和左边一个是不是可以合并，如果可以那么就把它们变成一个相同字符子串，压到优先队列中。这样会发现优先队列中有重复元素，那么就还需要判断一下当前取出来的相同字符子串是不是已经被干掉了。
最后需要快速输出来卡常。我甚至用了一个fwrite。。。
Codeforces 464 A
题意：给定一个字符串，求比这个字符串字典序大并且和它长度相等的第一个不含有长度大于等于2的回文串的字符串。
思路：首先我们枚举最后一个与原串相等的位置，从后往前枚举，因为我们需要的是第一个字典序大于给定串的。
然后就枚举我们将下一个字符改变成了什么，再按照这种方法继续填充完整答案串即可。
Codeforces 464 B
题意：给8个$(x,y,z)$三元组，但是每个三元组的内部顺序可能是错乱的，问是否有可能把这些三元组们调整顺序之后变成一个立方体的8个顶点。
思路：首先枚举每个三元组的顺序，然后判断这个是否是一个立方体：我们对于每一个顶点向另外7个顶点连边，如果这是一个立方体，那么得到的会是这些东西：
- 三个棱长
- 三个$\sqrt{2}$棱长
- 一个$\sqrt3$棱长
然后对于所有的都是这样就说明这是一个立方体。（其实我并不会证明
Codeforces 464 C
题意：给一个数字串，然后给n个询问：每个询问是$d_i\rightarrow t_i$，其中$d_i$是一个数字，$t_i$是一个数字串。代表的是将原串中所有的$d_i$都改变成$t_i$。问经过这些操作后原串表示的数字$mod\ 10^9+7$是多少。
思路：考虑dp。首先我们考虑i..n这些操作都处理完了之后会把c数字改变成什么，就记为$b[i][c]$。
然后就会发现我们在转移的时候需要变成$b[i][c]*10^{b[i+1][t[j]]的长度}+b[i+1][t[j]]$。
所以还要记录$10^{b[i][c]的长度}$，记为$a[i][c]$。
然后转移的时候就很好做了。
2019年3月20日
Codeforces 464 D
首先我们知道这K个装备是互不干扰的，就是说如果一个装备升级了或者卖掉了，不会对其它装备的挣到的钱产生任何影响。所以我们就考虑单独处理某一个装备挣到的钱。
那么就设$dp[i$][j]表示还剩下i个怪兽没有打，这个装备现在是j级别的期望挣到的钱数。
答案就是$dp[n][1]$。下面考虑转移。
首先如果这一轮拿到的装备就不是这一种，即有$(k-1)/k$的概率答案是$dp[i-1][j]$。
否则枚举这一轮拿到的装备是级别$l=1..j+1$，有$1/k/(j+1)$的概率答案是$dp[i-1][max(j,l)]+min(j,l)$。
但是这个转移是$O(n)$的，状态数是$O(n^2)$的，就非常不好。
下面先考虑优化转移。看第二种情况式子的形式，发现就是一个1加到j的和。
所以现在的转移方程：
$dp[i][j]=(k-1)/kdp[i-1][j]+1/k/(j+1)(dp[i-1][j]j+l)+1/k/(j+1)(dp[i-1][j+1]+j)$。
之所以需要将第二种情况拆分成两部分，是因为$l=1..j$和$l=j+1$是不一样的。
然后再来考虑优化状态。
仔细思考就会发现如果j很大，那么$dp[i$][j]对答案的贡献是微乎其微的，
因为每次都要除以k再除以j+1，那样是指数级的。
所以我们就可以把j比较大的一些状态给干掉。
经过试验发现我们把前1000个留下不会tle（雾），
所以我就只转移了$dp[i][1..1000]$，再加上滚动数组优化空间即可AC。
Codeforces 815 C
考虑树型dp。
$dp[i][0/1][k]$表示现在在第i个节点，
父亲节点有没有选用优惠，
这个子树中买k个节点所需要花的最小代价。
然后转移的时候枚举i的一个儿子u，
然后还要枚举在u的子树中选择了多少个节点l，
则$dp[i][0/1][k+l]=dp[i][0/1][k]+dp[u][0/1][l]$。
还要注意转移顺序。
最后枚举最后一个$dp[1][1][i]\leq limit$的i就是答案。
2019年3月21日
Codeforces 725 C
求出两个相同字符的位置，记为x和y。
然后考虑把相同的那个字符放在第一行的什么地方，
然后把x+1..y-1的部分一折两半，放在第一行的末尾再折回第二行。
再把1..x-1和y+1..n放下来就可以了。
Codeforces 725 D
题意：有n个队伍，你是第一个队伍的一员，然后你可以把你们队伍拿到的一些气球给其他的队伍，如果一个队伍的气球数量大于他们的质量，那么他们就会被删除。
然后你的排名是比你的队伍获得的气球数量多的队伍的个数$+1$。
问你最高能得到怎样的排名。
思路：我们看如果我们把气球给了某个队伍会发生什么。
- 这个队伍没有被删除，只是多了一些气球。（那还不如不给
- 这个队伍被删除了，并且我们的队伍少了一些气球。
所以我们给气球的目的是删除队伍，并且要花费最少的代价。
那么我们不断地删除比当前我们队伍气球多的队伍中需要花费最少的代价来删除它的队伍。
然后我们把它干掉，更新答案。
这支队伍可以通过优先队列来维护。
对于每一个气球数量大于我们队伍的队伍，我们都要把他们删除的代价放到优先队列中，并且还要实时更新。
一直到没有气球数量大于我们队伍的时候结束。
2019年3月23日
Codeforces 3 D
题意：有一个括号序列，其中一些位置是问号，把第$i$个问号改成(需要$a_i$的代价，把它改成)需要$b_i$的代价。
问使得这个括号序列成立所需要的最小代价。
思路1：
这个是正统的贪心。
首先我们假设所有的位置上都是)，那么我们在从左向右扫描的途中会发现一些问题。
比如：我们原来的序列是(??)，现在假设成了()))，那么在第三个字符处就会发现我们的打开的左括号数量为$-1$，这是肯定不行的，所以我们必须把第二个字符或者第三个字符改成左括号以把左括号数量变成$1$。
那么就可以想出一个贪心的方案了：
我们从左向右扫描，如果把当前的问号改成右括号不会使打开的左括号数量出现问题，那么我们就把这个问号待定成右括号；
然后如果出现了问题，我们肯定要把所有的待定问号（包括当前这个）中改动代价最小的改成左括号。
这样我们就可以把左括号数量重新加成正的。
然后我们怎么维护代价最小的待定问号呢？直接用一个优先队列或者一个$set$就可以了。
思路2：
这个是过不了的$dp$。
我们肯定是考虑到了第$i$位，打开的左括号数量是$j$，最小的代价。记为$f(i,j)$。
然后我们考虑转移。如果是左括号，那么转移到$f(i+1,j+1)$，右括号，转移到$f(i+1,j-1)$，问号，都要转移，同时加上代价。
可惜，这样会$mle$或$tle$。
所以考虑优化状态。（转移怎么优化啊。。。
首先我们记如果把从$i$开始的所有问号都改成右括号，会把打开的左括号数量减少多少为$suf_i$。
那么如果$j>suf_i$，即所有的一起上都消不掉$j$，或者$j\not \equiv suf_i (mod\ 2)$，即把一些右括号改成左括号不可能消掉$j$，那么这个状态就不要。
可惜这样还是会在第$31$个点上挂掉。
思路3：
这个是乱搞的线段树。
ly_61同学提出了用数据结构来优化贪心的方法，然后。。。
首先我们考虑把所有的问号都改成左括号。
然后把所有的问号的左括号改成右括号的代价从小到大排序。
然后按顺序一个个尝试把问号改成右括号，只要不会违背条件——在任何一个位置，这个位置为止打开的左括号数量大于等于$0$。
那么我们就可以用线段树来维护对于每一个位置打开的左括号数量。
我们把一个问号改成右括号所改变的是把从那个问号的位置开始一直到最后的所有位置的左括号数量$-2$。
改回来的代价是$+2$。（废话
然后就可以一个一个尝试辣
如果改到最后发现到最后那个位置的左括号数量不是$0$，那肯定无解。
这个正确性不是那么显然，但最优性显然。下证正确性。
首先如果把所有的问号都改成左括号时到最后一位的打开的左括号数量不是偶数，则肯定无解。
那么我们需要改的问号的数量也是显然的，不妨记其为$m$。
然后就可以发现如果我们每一次修改都可以成功的话至多修改$m$个问号。
那么就要证最少修改$m$个问号了。
我才不会告诉你我不会证了呢
根据上文，至少有$m$个问号使得我们把它们都改成右括号之后可以满足要求
所以我们扫描之后就可以得到$m$个？？？
（其实这个正确性很迷辣。。。
（这个“证明”一点也不像是个证明辣。。。
（反正能过的方法就是好方法。。。
（其实可能有反例的吧。。。
Codeforces 332 C
我爱对拍，对拍使我快乐。。。
题意：有$n$个议题，学生们会让议会同意$p$个，其中主席会执行$k$个，
每一个议题执行后主席会掉$a_i$的头发，不执行后议会会增加$b_i$的不开心值，
然后主席想让议会的不开心值最小，如果有多重方案就选自己头发掉的最少的；
而学生们想让主席的头发掉的最多，如果有多种方案让议会的不开心值最大。
问让议会同意哪$p$个会达到最好的效果。
思路1：
这是我的不对的思路。
（虽然没提交
我们首先将所有的数按照$b_i$从大到小排，如相等按照$a_i$从小到大排。
然后把前$n-p+k$个按照$a_i$从大到小排，
然后取前$k$个作为主席执行的
再向后延$p-k$个作为主席不执行的
然后其实这个是错的。
如果所有的$a$都相等，那么这个答案就不对
（我只是对拍出来的，并不会证。
思路2：
这是对的思路。
首先我们枚举主席执行的和不执行的所取的议题的范围的分界线$i$。
然后我们对于所有的$i$要找出主席取的和不取的最好效果的那些议题。
那就从前往后扫一遍，找出取的；
从后往前再扫一遍，找出不取的。然后取或不取都是放到优先队列里面找最大的$a$或$b$。
然后看答案最大的就可以了。
2019年3月24日
Codeforces 115 D
题意：给一个没有括号的表达式，问有多少种添加括号的方法使得这是一个合法的表达式？输入可能有正负号、加减乘除、数字。
思路1：
这是不能过的$naive$的$dp$。
考虑$dp(l,r)$表示从第$l$个字符到第$r$个字符有多少种添加括号的方法。
转移的时候就枚举当前最后一次运算。
思路2：
这是$tourist$的神奇$dp$。
考虑$dp(i,j)$表示第$i$个正负符号到第$j$个连续符号段连着的那个数字有多少种添加括号的方法。
转移的时候是枚举最后一次运算时哪一个连续符号段的第一个（因为只有这一个是二元运算符
那么就发现我们需要记录一个从连续符号段的第一个到连续符号段的第一个正负符号的映射，记为$st$。
然后从$dp(i,k)\times dp(st_{k+1},j)$转移来。
这样就三方出奇迹了。（%%% $tourist$）
思路3：
这是$shik$的神奇记忆化搜索。
首先我们把原输入变成以下段：
- 连续数字：0
- 正负（加减）符号：1
- 乘除符号：2
那么考虑$dp(i,j)$表示到了第$i$个段，打开的左括号有$j$个，有多少种方法。
然后考虑转移。
假如这个位置是连续数字，那么可以合上一些括号或者不合上。
否则就必须打开一个括号。
最后答案是$dp(n,0)$。
（话说1和2只是用来判无解的。。。
思路4：
这是ACRush的神奇三方DP。
按照shik的方法分段。
直接考虑$dp(i,j)$表示从第$i$段到第$j$段的答案。
然后转移的时候就是枚举中间那一个字符的位置，然后左右答案乘起来一加就可以了。
思路5：
这是$Al.cash$的和$shik$差不多的方法。
两人的状态是一样的，但是$Al.cash$用了前缀和来搞每次合上很多符号的操作对$dp$的影响。
思路6：
这是最难看懂的$chenlijie$神仙的方法。
首先把所有的连续符号段中的正负符号个数放到v数组中，
然后用一个$dp$的$vector$存下所有的$dp$值，
从后往前枚举v，对于每一个v，dp的前v+1个代表的是倒数的第*个正负字符到最后的答案。
然后把它们删掉，后面的内容做一次前缀和就竟然可以转移了！？
这。。。
感觉之前想的也不太对了。。。
其实是在思路1中$dp$每一次更新当前区间的时候加上的东西之和正好是后一个位置到结尾的答案。。。
这肯定是打表打出来的！
思路7：
NuM的，基本同ACRush。
把这些写完后一发交上去只过了一个。。。
其它的都是由于一个特殊情况没有考虑到：
如果第一个字母是乘号或者除号，那么无解
所以两个WA，两个RE。
然后第二发全过了。
2019年3月29日
Luogu P1074
题意：给一个数独，问怎么填会使每个位置填的数乘以它的权值得到的和最大。其中每个位置的权值在题面中给出了。
思路：首先我们考虑搜索。由于我们不可能搜每个格子取太多的数，所以我们从所能取的数少的格子开始搜索。
由于搜索的过程中肯定会每个格子能取的个数有变化，那么我们可以过一段时间重新排序。我将这个时间设为$30000$个时间单位（进入搜索的次数）。
然后每一轮搜索的时候我们取出第一个格子，然后枚举它填的数，进入下一层搜索。
我们可以将所有的格子放到$deque$里面，以便于取出第一个格子，又要塞回去。
然后就是要对于每一行、每一列、每一个九宫格都存一个所用的数的$mask$了。
Atcoder hbpc C
题意：给n个循环小数或者有限小数，问其中有多少个互不相同的。
思路：我的思路比较繁琐。
首先我们考虑分数化小数：假设原来的数是$a.b(c)$，那么这个分数就是$a+\frac{b}{10^{len_b}}+\frac{c}{10^{len_b}\times (10^{len_c}-1)}$。
所以用4哈希判一下两个是否相同，需要注意我们的哈希模数必须都要取质数，因为需要取$10^{\dots}$、$10^{\dots}-1$的逆元。
这里我取的是${19260817,998244353,1000000007,1000000009}$。
再用并查集看等价类的个数即可。（这里其实用一个$set$存一下所有哈希值就可以了。。。
其实还有一种更简单的思路：
我们直接将循环节重复几次，直到长度大于等于$600$为止。
然后我们将$0.999…$改成$1.0$，所有的直接进行排序，比较，然后就完了。。。
2019年3月30日
UOJ 17
题意：在$n\times m$的网格中有一些柱子，它们可以通过的区间是$(L_i,R_i)$，位置在$P_i$。在第i个位置点击一次会使高度增加$X_i$，不点击会使高度减少$Y_i$。可以重复点击，效果叠加。问最少需要多少次点击来通过这个游戏。或者输出最多能通过的柱子个数。
思路：考虑$dp(i,j)$表示到了$(i,j)$这个点的最少点击次数。
然后转移方程如下：$dp(i,j)=min dp(i-1,j-kX_{i-1})+k,dp(i-1,j+Y_{i-1})$。
但是这肯定只能拿$70pts$。
所以我们需要进行一些优化。我们记$min dp(i-1,j-kX_{i-1})+k$为$g(i,j)$，那么转移分为两步：
$dp(i,j)=min(g(i,j),dp(i-1,j+Y_{i-1})$
$g(i,j)=min(g(i,j-X_{i-1}), dp(i-1,j-X_{i-1}))+1$
然后就好了。
其实根本不用这样想，我们只需要这样转移：
首先从小到大枚举$j$，对于每一个$j$更新$dp(i+1,j+X_i)$为$min(dp(i,j),dp(i+1,j))+1$；
然后从小到大（其实这里无所谓）枚举$j$，对于每一个$j$更新$dp(i+1,j)$为$dp(i,j+Y_i)$。
这样肯定是对的，因为所有的$dp(i,j)$都更新到了$dp(i+1,j+X_i)$，然后又随着$dp(i+1,j+X_i)$到了$dp(i+1,j+2X_i)…$。
然后需要注意我们的答案在取的时候不要$dp(i,j)=\infty$的也取进去。。。
Codeforces 212 E
题意：给一棵树，其中删去一个点，剩余的联通块们同一个联通块都得涂同一个颜色（黑或白），问黑色涂的个数有可能是哪些。
思路：肯定是背包。
假设现在删掉$u$这个节点后剩下的联通块的大小们存在$V$数组内，
那么$dp(i,j)$表示到了第几个联通块，黑色涂了多少个是否有可能。
转移就是看当前的取不取。
即$dp(i,j)=dp(i,j) \vee dp(i-1,j-V_i)$
我第一开始笨笨地只是根所在的放到黑色，其它给白色。。。
其实这是没想清楚的体现。
2019年4月1日
UOJ 345
我会10分！
我们先把主链给剖出来。主链：从根开始一直往下走子树最大的儿子所构成的链
我们看如果我们要把$u$硬推到主链底下需要多少$u$的子树外部节点的帮助，记为$need_u$（u在主链上）。
那么$need_u=min\ need_v-(size_u-size_v-1$（这个是为了$u$本身减去的）$-1$（这个是为了把$u$推下一条边减去的）$)$
下面我们就看怎么把每一个主链外的节点推啊推到主链底部。
首先我们需要把它推到主链上。
记$u$的祖先中第一个在主链上的节点为$belong_u$。
下面就是看我们是否还需要再上推一点才够把它推到主链底下。
那就要计算我们将$u$推到某个在主链上的节点$v$再将其推下去到主链底端的代价。
是$dep_u-dep_v+\dots$（其中$\dots$表示的是主链最底端的深度减去$dep_v$）。
那么我们既然还需要把$u$推到底端后还推回到$v$，
就说明我们需要把$v$子树次大的儿子的子树中所有的给用光。
那我们可能还会剩下一点子树最大的儿子的子树，就是另外一个子问题了。
按照这样想，$dep_u-(dep_v+size_{largest_v}-size_{secondLargest_v})>0$。
所以对于一个$u$我们要找出最小的满足此条件的$v$，
就需要记录对于每一个$x$，$dep_v+size_{largest_v}-size_{secondLargest_v}>x$的最浅的$v$。
（因为要离根越近越好啊
那么分类讨论一下：
- $belong_u$甚至在$v$之上：那么只能推到$belong_u$。。。
- $belong_u$就是$u$：直接推下去就可以了。。。
- 正常情况：无。
然后看看$need_u$够不够就可以了。
2019年4月3日
LOJ 2144 84pts
首先$op2$很简单。直接并查集一搞就好了（话说我现在什么东西都要写个并查集有点。。。）
然后$op0$我不会，就直接$O(n^2)$枚举一下$P$这个人的路径，然后用$op1$的操作求答案。
所以只是看$op1$的复杂度决定了分数（逃。
我第一开始写的是$O(n^3)$的鬼暴力，然后拿了$60pts$跑路了。。。
现在是$O(n)$的。
首先我们把$P$的路径的一端挂到根上，这样做的好处就是我们不用考虑$P$父亲所在的新联通块了。
如果$H$是一条从祖先到儿子的链，那么我们可以通过$dp$来求出这条链会带来的新联通块数量
然后看我们把$H$放到哪里。分情况考虑。
- H0和H1的LCA在P0到P1的路径上：这时我们的$H$不会给LCA带来$son$ $size-2$个新联通块的改变。
- H0和H1的LCA不在P0到P1的路径上：这时$H$会给LCA带来$son$ $size-2$个新联通块的改变，但是LCA的父亲所在的联通块是否被添加了要看它的父亲是否被删除了
然后84分到手。
所以看样子$op0$也是树型$dp$？？？
LOJ 2145 100pts
这题。。。BT啊
首先我们很容易想出$dp(msk)$表示现在灯开关的情况是$msk$，期望通过多少步走到终结态。
很明显$dp(msk)=\frac{1}{n} \times \sum_{i=1}^n dp(msk\ xor\ M_i)$。
其中$M_i$表示把$i$这个灯按下之后会改变哪些灯的状态。
然后发现这个转移是有环的。。。所以高斯消元。
然后很开心地发现这个复杂度是$O(2^{3n})$的，
所以看看是不是可以合并某些状态。
观察得如果两个$msk$达到终结态需要的最少按的次数是相同的，那么他们的$dp$值也是相同的。
所以考虑改变状态为$dp(i)$表示最少要开关多少次灯来把当前状态变成终结态时期望的步数。
观察得转移是$dp(i)=\frac{i}{n}dp(i-1)+\frac{n-i}{n}dp(i+1)+1$。
很遗憾这个还是有环的。。。所以高斯消元。
这个复杂度就是$O(n^3)$的了，可以拿$60pts$（因为最后乘$n!$会爆炸）。
根据定义$dp(n)=dp(n-1)+1$。
那么我们看看$dp(n-1)=???$
根据定义$dp(n-1)=\frac{n-1}{n}dp(n-2)+\frac{1}{n}dp(n)+1$
$=\frac{n-1}{n}dp(n-2)+\frac{1}{n}dp(n-1)+\frac{1}{n}+1$
所以$\frac{n-1}{n}dp(n-1)=\frac{n-1}{n}dp(n-2)+\frac{1}{n}+1$
所以$dp(n-1)=dp(n-2)+\frac{n+1}{n-1}$。
那么我们可以假设$dp(i)=dp(i-1)+c(i)$。
那么根据定义$dp(i)=\frac{i}{n}dp(i-1)+\frac{n-i}{n}dp(i+1)+1$，
$=\frac{i}{n}dp(i-1)+\frac{n-i}{n}(dp(i)+c(i+1))+1$，
所以$\frac{i}{n}dp(i)=\frac{i}{n}dp(i-1)+\frac{n-i}{n}c(i+1)+1$，
简化得$dp(i)=dp(i-1)+\frac{(n-i)c(i+1)+n}{i}$。
所以$c(i)=\frac{(n-i)c(i+1)+n}{i}$。
做完了。。。
LOJ 2004 100pts
首先我们肯定要建AC自动机的。。
那么这题就肯定是个AC自动机上$dp$。
所以想想状态。
首先如果我们把状态设成这样行不行：
$dp(i)$表示匹配到了i节点的概率。
那么转移的时候就是$dp(i)=\frac{1}{2}\sum dp(go_i^c)$。
这样的转移是有环的。。。所以高斯消元。。。
但是！AC自动机的节点数是$O(n^2)$的。。。
所以T得飞起。。
那么试着改一改？
改为$dp(i)$直接表示第i个串第一次出现的概率？
那么转移很难啊。
如果我们当前的串为$S$，并且没有任何的串在其中出现过，设所有的$S$的概率综合为$fail$。
那么我们在$S$后硬生生地加上$s_i$，那么这个概率是$fail\times \frac{1}{2}^m$。
但是可能中间会有某个$s_j$出现。
那么现在的串可以变形成$S$的一个前缀$+s_j+s_i$的一个后缀
其中$s_i$的一个前缀和$s_j$的一个后缀匹配。（这不就是$fail$指针吗！
其中的概率是$dp(j)\times \frac{1}{2}^{len(suf(s_i))}$。
所以转移方程就出来了。
但是。。。这个还是有环的。。。所以高斯消元。。。
可惜我们只有$n$个方程，却有$n+1$个未知数。
但注意到所有串第一次出现的概率之和为$1$就释然了。
做完了。。。
2019年4月8日
JSOI2019Round1Day2T2
算法1
$n \leq 16$。
所以果断状压dp啊。
考虑$dp(mask)$表示$mask$集合里的节点分配段之后最少总内存和。
那么转移的时候枚举现在把$nmask$里的点都放到同一个内存段里面。
为了在$O(n\times 3^n)$的时间内完成整个转移操作，
我就用了$dfs$转移。。。所以代码就奇丑无比（循环调用
然后注意可以用$dfs$序来判断$u$是不是$v$的祖先。
（话说其实我们可以预处理一下，从每一个$v$往上跑。。。
所以复杂度$O(n\times 3^n)$。
预计得分：45
实际得分：45
算法2
注意到链的部分分。
我们假设链长这样：u--1--v
所以我们看怎么找$u$和$v$。
不妨设$u$是深度最大的那个节点。
那u--1的路径都用过了。
剩余节点中的最深的就是$v$啊。
那么再看怎么分组。
理性思考一下
只要在$u$到根的路径上最大的和$v$到根的路径上最大的配，
次大的配，然后某个没了就单独一组。
想一想为什么（我才不会说我是弄了个数据看出来的呢
就酱。
然后其实不用判断这个数据是否真的是链。。
因为我也写不出来其他部分分了
结合算法1即可。
但数据奇弱无比，还多过了两个点。。。
可能就是真正的分类方案最大的真的在最深的两条链上。。
预计得分：60
实际得分：70
Codeforces 650 A
思路：首先看式子
$\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}=|x_i-x_j|+|y_i-y_j|$
的唯一可行的情况是$x_i=x_j$或$y_i=y_j$。（因为两边之和大于第三边
所以就知道怎么做了。
- 第一种方法：我们维护三个$map$，分别存行、列、坐标是$\dots$的时候已经有多少个节点。
然后就可以边读边算，读到$(x,y)$这个坐标的时候把$ans$变成
$row_x+col_y-cnt_{(x,y)}$就可以了。 - 第二种方法：我们先读完所有的坐标，然后存同一个行、列、坐标各有多少个。
然后枚举每一个不同的行、列、坐标，算出
$\sum C_{row_x}^2+C_{col_y}^2-C_{cnt_{(x,y)}}^2$即可。
Codeforces 650 B
思路：二分/two pointers。
我只会二分了。。。
首先确定我们肯定是向左翻几个，再向右翻几个。（或者相反
那么我们就枚举向左翻到了哪一个（注意复制一遍原数组
然后二分右边到了多少个，用前缀和算一下代价。
然后two pointers看起来没多少人写？？？
注意代价要开long long。
Codeforces 650 C
思路：首先我们把每一行排序。
肯定现在相同的数在“压缩”过后也是相同的。
那就扔到并查集里面当做是一个节点。
然后如果$x$小于$y$就从$x$所在并查集的代表元向$y$所在的代表元连边。
这说明$y$的压缩后的值肯定大于$x$压缩后的值。
但这样边数是$O(n^2)$的。
注意到我们这样连边等价于我们只连同一行内大小连续的数的边。
这样就很可做了。直接一把$bfs$标记在$dag$上下推即可。
还可以直接拓扑排序后一个小小的$dp$。
其实没有必要正经地“拓扑排序”，只需要把所有的格子按照数的大小排就可以了。
因为从小的到大的连边啊。。。
那样就可以一个main函数干到底了（雾
2019年4月9日
LOJ 3049
这个D1T2绝对有毒。。。
首先我们构造一把反串的后缀自动机。
然后我们就需要找到每一个子串在SAM上的节点。
这个可以通过扫描线+树上倍增处理。
首先我们把所有的子串按照左端点排序，
然后从右往左扫描，在扫到$i$的时候：
我们取到$[i,n]$的子串代表的节点，
那么所有的$[i,j]$的子串都是这个节点在反串中的后缀！
所以所有的$[i,j]$的子串对应的节点都是$[i,n]$在$parent$树上的祖先。
那么就可以记$f[i][j]$为从$i$向上走$2^j$次$suffix$ $link$得到的节点。
然后倍增出每一个$[i,j]$的子串对应的节点就好了。
但这样会导致一些不同的子串对应到了同一个节点$i$，
我们假设$i$表示的子串们存在$v_i$中。
那么我们考虑构图。
首先我们把所有$v_i$按照长度从小到大排序，小的就是大的前缀
（根据后缀自动机节点的定义，以及构的是反串的SAM）
那么我们就可以把所有的B类向后面的所有A类连边。
但是这样的边数就是平方级的，所以要改一下：
所有的B类向下一个B类连边，以及向所有的下一个B类之前的A类连边。
还需要为每一个SAM上的节点向所有第一个B类之前的A类连边。
这样就可以做到同一个SAM上的节点内的前缀关系。
那么看不同节点的前缀关系怎么求。
这样就可以很自然地想到$suffix$ $link$。
把所有节点表示的最后一个B类向所有$link$指向它的节点连边。
因为这样可以从所有节点的所有B类走到另外所有节点的A类。
那么最后把控制关系连下边就可以直接$dag$上$dp$了。
如果存在环则答案必须是$-1$。因为环必须是包含A类串的。
2019年4月11日
LOJ 3049 分析
dxm
把每个SAM上的节点拆成$in_i$和$out_i$两个，
然后从$in$到$out$连边，
并且从$out$向所有$link$指向它的$in$连边。
我们现在考虑怎么把节点内部的A和B处理好。
我们肯定要从所有的B连向所有的A，而不能从A跑到另一个能计入答案的A，
所以我们把A分成$in$和$out$，
只有$out$是计入答案的，
那么我们对于同一个SAM上的节点这样连边：
- 从每个A的$in$连到$out$，并从$out$向所有支配的B连边。
- 从每个B，向长度大于等于它的第一个A的$in$连边，还要向该节点的$out$连边（要不然出不去
- 从这个节点的$in$向所有的A的$out$连边。
这样想十分的自然。
xyx
首先通过SAM上倍增求出每个子串的节点，
然后看怎么建图：
首先我们把每个SAM中的节点的$link$连到自己，
并且按照长度把这个节点对应的所有的子串排序，
每个B连向下一个B，同时连向所有下一个B之前的A。
再把每个A连向所有支配的B即可。
再跑个dp就行了。
wyj
类似xyx，
但是他是把同一个SAM上节点的A串和B串分开考虑了，
导致需要对于每一个B串二分出长度大于等于它的第一个A。
复杂度就多了一个$log$。
hhr
类似xyx。（一模一样？
csl
首先构造SA。然后我们把每一个A串拎出来，
构建一棵树，其包含了所有的子串，并且如果$u$到$v$有一条边，则要满足$u$是$v$的前缀。
但这棵树的节点数太多了，我们只需要包含A的，就引出了新的概念——虚树。
（吐槽：这玩意折腾死我了。。。
所谓虚树，是在树上找一个不连通的块，使得：
其包含所有的A串和所有A串两两的LCA们。
这就要求我们在线性时间内求出A串两两的LCA。
注意到两串的LCA就是他们的LCP，那么我们这样做：
先把所有的A串按照字典序排（其实就是按照他们在原树上的$dfn$
然后把连续两个A串的LCP加进去也作为A串
这个是一个结论一样的东西？？？可能就是最后用到的LCA们最多就是这里的吧。（删掉
emmm其实这$^{TM}$就是虚树的基本操作啊。。。
再用单调栈存现在的“有用”的点，
扫一遍排序过后的A串，每次一直弹栈直到栈顶是当前节点的祖先（当前节点的前缀
那么就可以确定连这条边。
Ah…怎么这么难啊
再把所有的B连到自己所属的节点就好辣
yjz
首先构造SA，然后每一个子串可以用$[l,r]$来一一表示，代表这个子串在排名$[l,r]$的前缀中出现。
这样就可以按照字典序把A串都排好（所属后缀的$rank$，长度）
那么B串是其前缀的A串们肯定是连续的。
感性理解一下：假设连续两个A串有一个$lcp$，那一段A串的$lcp$就是中间两两的$lcp$的$min$。
所以假如现在我们的某个B串是$A_i$的前缀，那么
那么我们就要从B串的一个点连向A串的一个区间
所以线段树优化建图（orz
再跑个$dp$就。。行了？？？
总结一下这题就是各种奇怪操作优化建图？？？
2019年4月14日
Codeforces 339 D
题意：给定$2^n$个数字，现在把它们进行如下操作：
- 相邻的两个数取$or$
- 相邻的两个数取$xor$
- 以此类推，直到剩下一个数。
问每次修改一个数字，最后得到的那个数是多少。
思路：线段树。
但是在$pushup$的过程中要看当前节点到底层的叶子距离有多长，
如果是奇数就$or$，否则$xor$。
单点修改，查询根即可。
Codeforces 1000 F
题意：给一个序列，每次查询某个区间内一个只出现一次的数。
思路：线段树。
首先我们看只出现一次的本质是什么。
如果一个数$x$在$(l,r)$中只出现了一次，那么它在其中第一次出现位置为$p$，其下一次出现肯定大于$r$。
那么我们就有一个想法：
用线段树维护每一个数的下一次出现，那么区间中最大的一个还没有超过区间的右端点，则说明肯定无解。
但是我们只能够存下这个区间中每个数的第一次出现。
只好离线处理。
把所有的操作按照左端点排序，然后：
从右往左扫描所有的点，遇到一个新的就把当前的值下一次出现记录，同时把下一次出现“删除”。只用把其设成$-\infty$即可，因为足以让其不能参加取$max$。
这样就好了。
线段树需要单点修改、区间查询。
所以果断$zkw$。跑的飞快。
TangentDay：莫队。首先把操作离线，把他们按照左端点排序。维护一个（l,r）表示现在处理到的区间。
然后假设现在我们考虑的区间是（nl,nr），那么我们需要从（l,r）”挪”到（nl,nr）：
不断把r右移直到r>=nr，同时把路上的所有数出现次数加1，同时维护所有的现在出现次数为1的数的集合。
不断把l左移直到l<=nl，r左移直到r<=nr，l右移直到l>=nl。
这个顺序是不能改变的。因为如果先左移r或者先右移l可能导致区间长度为负数。
但这个复杂度是O(q sqrt(n) log(n))的，TLE。
ivan100sic：BIT套set。首先把操作离线，把他们按照右端点排序。
维护一个BIT表示每一个后缀出现的数字有哪些是只有一次出现的。
然后就发现我们需要的是区间修改+单点查询。
从左往右扫描右端点，每到一个新的点就把（上一次出现，上上次出现）的那段区间干掉，并且加入（这次出现，上次出现）这个区间。
查询的时候就看左端点上有多少个第一次出现了。
但这个复杂度是O(q log(n)^2)的，TLE。
修改了几次都没有效果。
ei133333：线段树套set。其实和ivan100sic差不多，只是他单点修改，区间查询了。
这样其实想的更自然？？？可惜还是TLE。
ei133333：线段树。还是离线操作，并且从左往右扫描右端点。
然后每次加入（这次出现，上次出现）这个区间，但不删去（上一次出现，上上次）这段，留着，当查询的时候删。
这里就发现线段树中维护的是一堆（数，出现位置）这个pair，
查询的时候把这个节点的所有pair中出现位置不是最后一次出现位置的干掉。
应该能AC了。复杂度O(q log(n))
natsugiri：线段树。强烈谴责该选手比赛贴板子的恶劣行为，并禁赛三年。（删掉
然后就和上课讲的方法差不多了。
krijgertje：莫队。和TangentDay类似，只不过他用的是链表，消掉了一个log。
然后他的排序方式也不一样：先按照左端点排序，如果左端点是奇数，则右端点按照从小到大排序，否则从大到小。
可惜复杂度O(q sqrt(n))，还是TLE。
krijgertje：线段树。和上课讲的方法一模一样。
总结：出题人很厉害，
O(q sqrt(n))的方法在第8个点TLE了，
O(q log(n)^2)的方法即使过了第8个点还有第9个点，
都安排上了。
但是莫队还是可以过的。
思路2：莫队。
我们在加入、删除一个数的时候这样处理：
我们记录这个数是否只有一次出现，并且记录这个数所在的块中有几个只有一次出现的。
块的大小自定。取$O(\sqrt{n})$可以达到最好的效果。
那么再看我们怎么找到第一个只有一次出现的数。
首先我们沿着每个块跑，看这个块中有没有。
如果有就进块内跑，找到第一个有的就是辣。
可惜隔壁线段树不知道比它高明到哪里去了，跑的比香港记者还快
但是可以贴着时限过。
Codeforces Round 1153（div. 2）
这场奇差。ABCD四题。179名。
但是E在现场有213个人做出。
描述一下我在35分钟做完D后的心路历程。
首先看到这道E，第一下想到的是把所有的横向和竖向的整列（行）求出相连的个数。
然后想如何能够用这个方法求出每一个格子周围的个数。
后面举了大概半个小时的例子。
最后才得到结论：不行。
这里是第一个失误点：没有在一条道走到黑的时候及时换思路。
然后的半个小时在尝试另一种方法：先求横竖再二分。
也得到了相同的结论：不行。
这里是第二个失误点：没有吸取之前的教训来更换方式。
最后十分钟的时候想到了正解，然后赶紧码码码。
可惜样例都没过。
然后比赛就结束了。
所以：
及时更换思路（这个其实是老生常谈了，可能我对自己信心太强？才导致了我对于一个思路“情有独钟”。
发现错误一定要改！！！
唉。
可能到了后面心情也有点小起伏吧。
虽然不知道外界的情况，但是看着时间一分一秒过去，每一次抬头都会过掉10分钟以上，还是有点紧张的。
所以：
不管什么情况，好 好 专 心 做 题！！！
唉。
其实这些东西很早之前都讲过。
但是。。。我又有哪些一直改的很好呢？
不是这场比赛FST了1题，又是那场没做出来。
下次努力？
拓宽思路。
平常看的那么多程序都给狗吃了啊。
如果平时的思路十分开阔，我也许就不会卡在一种道路上太长时间了。
考试策略。
可以看看F。也算个调剂。
所以：
平时的努力+考试的策略、方法=成功。
但：这些东西都是很早之前就讲过了的！！！
可能是我平时不够努力吧。
这场考试也不算太。。平稳？
2019年4月16日
AGC 011 F
题意：给$n+1$个站$0,\dots,n$，连续的两站$i-1$和$i$之间有一个距离$A_i$，其是单行（$B_i=1$）或双行（$B_i=2$），单行线不能同时有两辆方向不相同的车在上面，现在每$k$分钟发一次车（从$0$到$n$和从$n$到$0$），需要安排$k$分钟内的时间表，使得从$0$开到$n$的时间和从$n$开到$0$的时间和最小。
思路：主席树优化$dp$。
这道题告诉我们要学好语文
首先避免在单行线上交叉的方式是在站台上停留一段时间。
假设我们从$0$到$n$的过程中停在第$i$个站台的时间是$p_i$，从$n$到$0$的过程中停在第$i$个站台的时间是$q_i$。
那么我们看在第$s$个段中它们的时间区间是怎样的。
$0\dots n$：$[\sum_{i=1}^{s-1} p_i+\sum_{i=1}^{s-1}A_i,\sum_{i=0}^{s-1}p_i+\sum_{i=1}^{s}A_i]$
$n\dots0$：$[\sum_{i=s}^{n}q_i+\sum_{i=s+1}^nA_i,\sum_{i=s}^nq_i+\sum_{i=s}^nA_i]$
题目要求的就是这两个区间在$mod\ k$意义下不相交。
但是这样的式子比较丑，没办法化简，
所以我们换一种方式表示$n\dots0$的时间区间。
既然是模意义下的，我们就假设它在$0$出发，“倒退”回$n$。
那么它的时间区间就是$[-\sum_{i=0}^{s-1}q_i-\sum_{i=1}^sA_i,-\sum_{i=0}^{s-1}q_i-\sum_{i=1}^{s-1}A_i]$。
我们要求这两个区间不相交，就是第一个区间的两个端点都不在第二个区间内。
移项得$\sum_{i=0}^{s-1}p_i+q_i\leq-2\sum_{i=1}^sA_i$
或者$\sum_{i=0}^{s-1}p_i+q_i\geq-2\sum_{i=1}^{s-1}A_i$。
即$\sum_{i=0}^{s-1}p_i+q_i$不在$(-2\sum_{i=1}^sA_i,-2\sum_{i=1}^{s-1}A_i)$内
即$\sum_{i=0}^{s-1}p_i+q_i$在$[-2\sum_{i=1}^{s-1}A_i,-2\sum_{i=1}^sA_i]$内。
那么题目转化成了这样的东西：
一个人在数轴上走路，起初在任一点，只能向右，
要求某些整数时间点时他的位置在模$k$意义下属于区间$[L_i,R_i]$，
问他最少走多少距离。
首先确定我们肯定只会走到端点上。
那么把所有端点离散化。
然后考虑一个很$naive$的$dp$。
设$dp(i,j)$表示现在在第$i$个段，
目前的位置$mod\ k$在第$j$个离散化后的端点处，走到第$n$段的最小代价。
那么转移的时候就从$dp(i+1,*)$转移来就好辣。
可惜这个方法只能过500分的点。
那我们换一种思路。
考虑$dpL(i)$和$dpR(i)$表示到了第$i$个段，
现在在$L_i$还是$R_i$，走到第$n$段的最小代价。
转移以$dpL$为例。我们看现在如果一直不走最多到哪里会不可行，假设这个点为$j$，
那么我们就从$dpL(j)+L_j-L_i$转移就好了。
但是求$j$的过程是$O(n)$的，肯定$TLE$。
那么就要看这个$j$的性质。然后发现并没有什么性质
所以我们用主席树维护每个新区间放下的时候每个点被覆盖了多少次。
但是主席树只能单点修改。所以果断差分。这样空间就得开的很大很大（我开了1e7。。。
如果在$i\dots j$的这段区间内所有新区间都覆盖$L_i$，那么自然是极好的。
直接二分$j$即可。复杂度$O(n log(n)^2)$。
再看怎么求答案。
首先我们还是从一个$L_i$（或$R_i$）开始，一直走走走到$i$，再加上$dpL(i)$即可。只是需要判断是否中间不能走了。
主席树真$^{tm}$难写。中间还出现了一些幺蛾子。。。
人生第一棵主席树祭