又快退役了，所以写写一句话题解。
看起来好像有点数位dp的感觉；根据套路，如果在某一位上(b_i<a_i)，那么之后这一位上就可以随便填了，而这个可以随便填的数我们就钦定它有调节作用，无论其他数异或的结果是什么，都可以通过这个数调整成目标结果。
我们枚举一个数位(k)使得(b_i)高于数位的部分都和(a_i)相等，之后搞个(dp)，设(dp_{i,0/1,0/1})表示处理了前(i)个数，(k)位上的异或值为0/1，是否钦定了调解数；考虑从(i)到(i+1)转移，如果(a_{i+1})在第(k)位是0，那么后面随便选一个小于剩余部分的数即可；如果是(1)，我们就考虑一下是否钦定其为调节数。这样就可以写一个(O(Qnlog w))的暴力了。
不难发现这个dp随便就可以矩乘优化，线段树维护一下，复杂度(O(nlog nlog w))。http://zhengruioi.com/submission/212421
一个暴力的想法，枚举一个子矩形，求交恰为这个子矩形的方案数有多少；我们发现做这个的时候大概就需要容斥一下，设(F(n,m))表示交至少为(n imes m)子矩形的方案数，发现只需要算(F(1,1)-F(1,2)-F(2,1)+F(2,2))。于是我们需要对于这四种大小的矩形求有多少个矩形将其包含。
现在有了一个(O(n^4))的做法，以求(F(1,1))为例，枚举一个全(1)子矩形，考虑这个子矩形包含了哪些(1 imes 1)大小的子矩形，这个影响就是一个子矩阵加(1)，差分一下即可。(F(2,1),F(1,2),F(2,2))同理。
我们发现差分实际上跟矩形的四个顶点有关系，我们只对每个点求其是多少个矩形的右下/右上/左下/左上顶点即可。经典问题，单调栈就能做到(O(n^2))，统计答案的时候需要快速幂，于是复杂度是(O(n^2log k))。http://zhengruioi.com/submission/212100
显然的dp是，(dp_i=1+sum_{j=1}^{i-1}S_{i,j}dp_j)，其中(S_{i,j})表示矩形(i)和矩形(j)交的的面积。
一个显然的等价转化，求出(dp_j)后将矩阵(j)都加上(dp_j)，求(dp_i)的时候只需要求矩形(i)的和；显然可以CDQ分治后转化为一个二维数点问题，一个小trick是将加转化为后缀加，查询的时候前缀查，可以省去一定程度上的讨论，复杂度是(O(nlog^2 n))。http://zhengruioi.com/submission/209812
dp一下，两种转移(dp_i=dp_{i-1}+p,dp_i=min_{j<i}dp_j+q)第二种转移需要满足(S[j+1:i])是(S[:j])的子串。
我们设(r_i)表示(dp_i)能远能转移到哪里，不难发现存在(r_ileq r_{i+1})，于是利用这个单调性直接SAM来求出r$，之后跑一个单调队列优化这个dp就好；
求(r)的过程大概就是动态建SAM，之后暴力往后跑；从(i+1)到(i)的时候这个子串少了一个字符，需要跳一下(parent)树上的父亲。
- IOI2018 seats https://www.luogu.com.cn/problem/P4898
考虑如何判断一个(k)是否合法。我们称权值不超过(k)的点为黑点，大于(k)的为白点；首先矩形得是个封闭图形，不能凸也不能凹，于是对于任何一个白点不能有超过两个与其相邻的黑点，否则就会形成一个凹或凸的角；之后我们还得保证矩形只有一个，我们考虑在左上角统计，于是左边和上边都是白点的黑点只能有一个；这是构成一个矩形的充要条件。
设(x)为左和上都是白点的黑点个数，(y)为和至少两个黑点相邻的白点个数，我们要求的就是有多少个(x=1,y=0)；由于(xgeq 1,ygeq 0)，所以等价与求有多个(x+y=1)；我们对于每个点考虑其为黑点和白点时的贡献，发现都只是一个区间加，于是线段树维护区间最小值和区间最小值个数即可，复杂度(O(nlog n))。https://www.luogu.com.cn/record/30554861
- BZOJ3853 GCD Array http://darkbzoj.tk/problem/3853
设(a_i=sum_{j|i}b_j)，我们把修改放到(b)序列上来做，查询(sum_{i=1}^xa_i)等价于查询(sum_{i=1}^xlfloor frac{x}{i} floor b_i)，直接整除分块查询即可；
考虑一次修改对(b)序列的影响，实际上对于(a_x+=[(x,n)=d]v)，即([(frac{x}{d},frac{n}{d})=1]v)，设(k=frac{n}{d})，相当于加上了(sum_{t|k,t|frac{x}{d}}mu(t)v)，即(sum_{t|k,td|x}mu(t)v)，于是我们枚举(k)的约数(t)，给(b_{td})加上(mu(t)v)即可。http://darkbzoj.tk/submission/56729
- AGC019F Yes or No https://www.luogu.com.cn/problem/AT2705
不妨设(m>n)，显然Yes和No哪个剩的多就猜哪一个，当一样多的时候就随便猜一个，期望对(frac{1}{2})个；不同的Yes/No序列共有(inom{n+m}{n})中，我们可以转化成一个格点问题，把一序列转化为一条从((n,m))走到((0,0))的路径，往下走是Yes，往左走是No；当在(y=x)这条直线上面时，会猜Yes；在(y=x)下面时，会猜No；于是猜对的次数就是(y=x)以上往下走的距离加上(y=x)以下往左走的距离，每经过一次(y=x)会随便猜一个，期望对(frac{1}{2})个；把图画出来，发现对于任何一种情况，那个距离都是(max(n,m))（大概是因为(y=x)把这条折线分割成了一些等腰直角三角形，于是(y=x)以下往左走的距离等于(y=x)以下往下走的距离），于是我们只需要算会经过几次对角线就好，枚举对角线上的一个点((i,i))直接组合数计算就好了，复杂度是(O(n+m))的；https://www.luogu.com.cn/record/30636733
不难发现({ m SG}_m(n)=nmod (m+1))，所以要对(min [2,n+1])求(displaystyle igoplus_{i=1}^n a_imod m)；考虑枚举一个(m)，之后枚举(l=km,r=(k+1)m-1)，那么对于(iin [l,r])，(imod m=i-km)；设(c_i=displaystyle igoplus_{j=1}^n [a_j=i])，那么我们需要求的就是(displaystyle igoplus_{i=l}^r [c_i=1](i-l))；这个式子可以拆位来求，需要套一个数据结构来求区间和，求一次是(O(log^2 n))的，枚举(l,r)的复杂度是调和级数的，所以整体是(O(nlog^3 n))的，比暴力没多几分；
考虑搞一个厉害的数组(f_{i,j})表示(xge i)且(x-i)的第(j)位为(1)的(c_x)的和，(f_{i,j}=f_{i+2^{j+1},j}+displaystyle sum_{k=i+2^j}^{i+2^{j+1}-1}c_k)，(i+2^{j+1})相比(i)多的是更高的一位，因此(x-i-2^{j+1})第(j)位上是(1)，(x-i)的第(j)位上也会是(1)，之后([i+2^j,i+2^{j+1}-1])和(i)的差是([2^j,2^{j+1}-1])显然在第(j)位上都是(1)；再来考虑有了厉害的(f)如何处理一个询问([km,(k+1)m))，按位考虑，我们设(t)为最小的(ge (k+1)m)且(tequiv km(mod 2^{j+1}))，那么答案就是(f_{km,j}-f_{t,j})再减掉一个区间的贡献，这段区间是([max(t-2^{j+1}+2^j,(k+1)m),t-1])。于是复杂度是(O(nlog^2 n))。http://zhengruioi.com/submission/215680
http://zhengruioi.com/download.php?type=tutorial&id=1286 300iq的题解 http://zhengruioi.com/submission/215798
- HDU 6429 https://vjudge.net/problem/HDU-6429
(i)向(p_i)连边后会出现若干环，考虑对于每一条边计算贡献，设(dp_{i,j,k})表示处理了前(i)个点，有(j)个点的出边没有确定，当前贡献为(k)；(j)个点的出边没定，就说明有(i-j)条出边定了，即(i-j)个点有了入边，也就是(j)个点的入边没有定；考虑从(i)向(i+1)转移的时候，(j)条没定的出边和入边都会跨过(i)，于是贡献是(2j)，由于最后总贡献一定是偶数，所以当成(j)来算最后乘(2)就好了；转移的话就考虑一下(i)是否往前面连一条边，是否被前面的一条边连过来，复杂度是(O(n^4))的；
考虑把(i)染色之后会影响哪些点，大概就以下四种：
-
(x_j>x_i,v_j<v_i)，(j)会被(i)追上之后被染色。
-
(x_j<x_i,v_j>v_i)，(j)会追上(i)之后被染色。
-
(x_j>x_i,v_j<displaystyle max_{x_k<x_i}v_k)，即存在一个(k)速度比较快，追上了(i)被染色，之后有追上了(j)将其染色。
-
(x_j<x_i,v_j>displaystyle min_{x_k>x_i}v_k)，即存在一个(k)速度比较慢，被(i)追上后被染色，又被(j)追上将其染色。
设(l_i=displaystyle min_{x_k>x_i}v_k,r_i=displaystylemax_{x_k<x_i}v_k)，根据上面情况我们发现，如果(v_jin [l_i,r_i])，则(j)就会被(i)染色；于是我们可以按照速度排序，那么染某个点相当于染一段区间，于是我们现在把问题转化成了问区间覆盖方案数的问题，把区间按照右端点排序后前缀和优化dp即可；复杂度(O(nlog n))。
将前缀和视为正数抵消负数的过程，一个正数能影响的只有下标大于它的数；
我们倒着扫一遍序列，每遇到一个正数我们就把它拿出来抵消后面的负数，显然应该优先抵消较大的负数，因为无论多大的负数都需要(1)的代价删除，优先抵消较大的负数能使的最后剩下得负数尽量少；
之后我们将剩下的负数从大到小排序，做一个前缀和，二分一下(b_i)能抵消掉多少即可；复杂度(O((n+m)log n))。
设(f_{i,j,k})表示当前处在点(i)，子串匹配到了(j)位，子序列匹配了(k)位距离终点的期望距离；子串匹配搞一个kmp自动机，子序列匹配就看一下转移的字符是否为下一个字符就好了，一般图随机游走高斯消元即可，这样复杂度是(O((n|a||b|)^3))。
我们发现子序列匹配的时候匹配的长度不会变短，即按照第三位来把转移图分层，层与层之间不会出现环，于是我们可以对分层高斯消元，复杂度(O(n^3|a|^3|b|))；著名睿智选手asuldb由于没有脑子，忘了期望要设成到终点的期望距离，之后自闭了。