[杂题闲说]DLS Round

感觉跟PPL的 JZM的询问3 有点像。
我们可以将 $4$ 个数分成 $2$ 段，相当于我们前 $2$ 个数的异或只要与后两个数的异或值相等。
显然，我们可以先把前面的二元组 $(x,y)$ 的异或值存在 $y+1$ 里面，离线下来。
再从后往前更新后面的二元组 $(z,w)$ 的异或值，这时候再将之前的异或值拿出来，扫到时看有多少相同的。
时间复杂度$O\left(n^2\right)$。

code(干脆这篇文章就都放链接了)

个人感觉这道题才是这场最难的，我想得最久。
$$(p-1)(p-1)=p^2-2p+1=(p-2)p+1$$ 所以我们代表 $p-1$ 的数字不会再最高位上出现。
我们找到那个数没在最高位上出现就可以找到 $p-1$。
$$(p-1)x=(x-1)p+(p-x)$$ 所以我们用 $x$ 与 $p-1$ 相乘就可以在最高位得到 $x-1$ 代表的数字。
不断这样推下去，就可以得到 $[1,p-1]$ 中所有数字对应的数字。
剩下一个没用的就是 $0$。
时间复杂度 $O\left(p^2\right)$。
code

显然，我们可以对于每一位单独求有多少中方法在这里出现了 $4$。
对于 $n⩽40$，很容易猜到分成左右 $20$ 个，最后合起来求答案。
如果要在第 $i$ 位得到 $4$，我们显然只需要去考虑第 $i$ 位及其之前的数位。
我们不妨用双指针的方式，将所有数按第 $i$ 位之前的数的大小排序，再记录下左边的数在右边对应的和为 $[4\times 10^{i-1},5\times 10^{i-1})$ 与 $[14\times 10^{i-1},15\times 10^{i-1})$ 的区间，这两个区间的大小就是左边数的答案。
由于我们是的 $i$ 是不断增大的，我们后面用来排序的位数也就越来越多，显然，这可以用一个基数排序的形式来维护数的顺序。
时间复杂度 $O\left(2^{\frac{n}{2}}{\log }_{10}{2}^{\frac{n}{2}}\right)$。
code 有点卡常

经典的隔板 $dp$，我第一次觉得的时候还以为有事什么高科技来着。
跟那个只维护 ${\sum }_{i=1}^{n-1}|a_i-a_{i+1}|$ 的题好像是一样来着。
将 $a$ 按照大小排序，然后 $dp$。
定义 $d{p}_{i,j,0/1,0/1}$ 表选到第 $i$ 个形成 $j$ 段，左右端点有没有被选。
然后 $dp$ 就行了，只是每个 $dp$要维护前 $K$ 大的值与对应的方案数，打着有点想吐。
时间复杂度 $O\left(n^2{K}^2\right)$。
code

关于二进制串模 $3$ 的余数应该很容易联想到 按位或。
对于这些二进制位我们可以其模 $3$ 的余数将其分为模 $3$ 余 $1$ 和模 $3$ 余 $2$ 两类。
假设我们模 $3$ 余 $1$ 与模 $3$ 余 $2$ 分别选取了 $x,y$ 个，显然应该满足 $3|x+y$。
我们实际上没有这么麻烦，我们可以直接将我们可以得到的最大数与最小数暴力选出来，再在其上面进行调整。
显然我们改变一个 $1$ 的位置最多会给我们造成 $1$ 的影响。
如果当前串模 $3$ 余 $2$ 就将一个在模 $3$ 余 $1$ 上的 $1$ 挪到余 $2$ 的位置上。
如果当前串模 $3$ 余 $1$ 就将一个在模 $3$ 余 $2$ 上的 $1$ 挪到余 $1$ 的位置上。
每次就挪动最小/最大的位置，这样造成的影响是最小的。
显然，只挪动一个位置是优于挪动多个位置的。
无解可以预先判一下。
时间复杂度 $O\left(T(n+m)\right)$。
code

我们记 $h_i$ 表示 $i$ 的因子个数。
容易得到结论，$Ans={\prod }_{i=1}^n\left({\sum }_{j=1}[h_j=i]\right)!$。
因为 $h_i$ 相同的球显然是可以自由交换位置的，所以内部的方案就是个数的阶乘。
而 $h_i$ 不同的球之间是独立的，就以乘法的方式结合。
显然我们可以把所有询问离线下来排序，用筛子求出所有 $i$ 的 $h_i$，从左往右扫维护答案。
这样做的话是 $O\left(T\log T+n\log n\right)$。
但这样的话只能拿 $70pts$，肯定是不行的。
这时我们可以发现一个特别之处，$p=5\times 10^5+9$，这是一个非常小的质数。
这意味着当每个相同的 $h_i$ 出现了超过 $p$ 次，我们的答案就一定是 $0$了。
实际上大约 $t=2250000$大概就是 $0$ 了。
所以我们实际上可以做到 $O\left(T\log T+t\log t\right)$。
实际上我们的筛子是可以做到线性的，但笔者懒得写了。
code

十分经典的题了，查询一个三角形内点的个数。
既然三角形的面是斜的，我们自然也得考虑将整个面斜过来维护。
我们可以把询问都给离线下来，我们可以先不考虑三角形，就看三角形的那一段斜行中有多少点。
这显然是一个差分的过程，我们只需要统计横纵坐标和小于等于 $x+y+d$，大于等于 $x+y$ 的点有多少就行了。
但三角形有该怎样处理呢？
我们可以再差分一下，先形象化的用图形表示，

显然，这两种颜色的区域它们的纵坐标都是大于等于我们的 $y$的。
而绿色的区域它们的横坐标又是小于$x$的。
我们可以借助这两种性质将其差分出来。
我们就按$x+y$轴的顺序不断加入点，查询。
以上两种特性的点都很好用树状数组维护，所以我们只需要在过程中维护两个树状数组就可以了。
时间复杂度$O\left((n+q)\log (X+Y)\right)$
code

经典的 $n⩽40$，这什么做法就不用我多说了吧。
我们很容易想到给它分两半状压。
前一半的 $dp{1}_S$ 表示前一半后缀和奇偶状态为 $S$ 的序列的方案数。
后一半的 $dp{2}_S$ 表示后一半前缀和奇偶状态为 $S$ 的序列的方案数。
我们在统计这两类 $dp$ 时答案只需要考虑满足完全被包含在前后半内的限制。
紧接着，我们可以发现一个点的前后缀奇偶性会对我们的答案产生贡献当且仅当它是某个限制的左右端点。
如果一个点是某个限制的左右端点，我们称其为关键点。
我们可以从原先的 $dp$ 状态中保留下我们的关键状态，记作 $g$。
对于每个关键状态 $g_{S^{\prime }}$，显然，它在另一半中对应的关键状态不会超过一个。
我们将它与这个关键状态的组合贡献到答案。
这样就很容易求出答案了。
对于求出最小的一个符合条件的序列，有了上面的 $dp$ 过程就很好想了。
我们只需要先枚举前一半的序列，找到最小的可以贡献到答案的前一半序列，再去找它的后一半序列即可。
时间复杂度 $O\left(2^{\frac{n}{2}}(n+m)\right)$。
其实如果再多记录点状态的话所不定可以将后面的 $n$ 或者 $m$ 优化掉。
笔者的写法常数可能有点大。
code

明摆着的签到题。
事实上我们可以将 $a$ 按大小排序，找到末尾开始的没有两个相邻的元素间隔超过 $K$ 的最长段就行了。
显然，这些点都是可以一个一个赢下去成为最大点的。
时间复杂度 $O\left(n\log n\right)$。
code

果然T2才是最难的
经典的统计题。
我们应该很容易联想到括号树的模型 （大雾）。
我们可以对经过某种颜色的路径数单独统计，将所有的路径数加起来求和。
我们将该种颜色的点标记为关键点。
经过关键点路径可以被简单的分为两类：

• 顶端的 $lca$ 是关键点。
• 顶端的 $lca$ 不是关键点，但该路径其它部分经过关键点。

第 $1$ 类路径只要统计每个点子树内的经过顶点的路径就行了，可以预处理出来。
我们可以将所有关键点按照它们的 $dfs$ 序排序加入，用栈维护能够完全覆盖当前关键点的关键点。
显然，如果要统计我们的第 $2$ 路径的话，我们可以对当前点求不经过它最近的关键父亲的路径 $2$，经过最近关键父亲的路径 $2$ 在那个父亲上去统计。
所以我们只需要看它在那个父亲的子树内还能匹配多少没有被已加入的关键点覆盖的点就行了。
显然，这样的话统计每种颜色就只需要排序后用单调栈维护了。
还有就是找它在关键祖先的哪个儿子内需要倍增维护，其实不用倍增也是可以的，不过那还要将所有儿子按 $dfs$ 排序，太麻烦了。
时间复杂度 $O\left(n\log n\right)$。
code只有90pts，没过的点我怀疑是数据问题。

老经典题了
显然，公倍数为 $2^i{3}^j$ 的集合数量可以通过差分求出。
我们记 $cn{t}_{i,j}$ 为 $2$ 的幂比 $i$ 小，$3$ 的幂比 $j$ 小的数的个数。
显然，$2^i{3}^j$ 的集合数量为 $2^{cn{t}_{i,j}}-2^{cn{t}_{i,j-1}}-2^{cn{t}_{i-1,j}}+2^{cn{t}_{i-1,j-1}}$。
这显然是个差分的结构，$(2^{cn{t}_{i,j}}-2^{cn{t}_{i,j-1}})-(2^{cn{t}_{i-1,j}}-2^{cn{t}_{i-1,j-1}})$，我们就维护一个 $2^{cn{t}_{i,j}}-2^{cn{t}_{i,j-1}}$
。我们考虑加入一个 $2^i{3}^j$ 数的时候，$2^i{3}^x$ 的集合数量会怎么变化。

• $x<j$，显然不会发生变化。
• $x=j$，会增加 $2^{cn{t}_{i,j}}$。
• $x>j$，会增加 $2^{cn{t}_{i,j}}-2^{cn{t}_{i,j-1}}$。

显然，以上的操作都可以用线段树维护，第二个是单点修改，第三个是区间乘法。
我们可以考虑枚举 $i$，不断将 $2^i{3}^x$ 的数加进去，对线段树产生修改。
在线段树上对于每个位置增加一个 $3^x$ 的系数，每次加完 $2^i{3}^x$ 的数后，得到这一层的和了，在减去上一层数，再乘上一个 $2^i$ 就可以得到这一层的贡献了。
时间复杂度 $O\left(n\log n\right)$。
code

相当巧妙的区间 $dp$。
显然，我们是有一个 $O\left(n^3\right)$ 的 $dp$ 做法，对于每个 $d{p}_{l,r}$，直接枚举下一个选择的数进行转移。
我们可以考虑改变一下我们 $dp$ 转移结构，来优化我们的 $dp$。
我们可以对于每个匹配了的，只记录它匹配的右端点，左端点不断移动，去寻找下一个匹配点。
当前的左端点如果能够不超过右端点，跳到右端点的左边下一个与左端点一样的点去更新 $dp$。
但这样统计方案就会遇到问题了，我们不能统计本质相同的串。
我们不妨假定我们左边一定是能跳当前字母就跳，也就是说如果一个字符之前已经跳过了，我们再条一次时就要减去它先前在相同的右段点处跳的权值。
也就是说，它这里会跳的权值也就是左端点在这个点之前第一个与它相同的字母到它这个区间内与该右端点匹配的 $dp$ 值。
这样，我们整个 $dp$ 就是 $O\left(n^2\right)$ 的了。
我们只需要在每次跳的时候都将当前跳的答案贡献到总答案中去就行了。
code

期望 $dp$ 模板。
记录 $d{p}_{i,j}$ 表示取完 $i$ 个瓜子，$j$ 个瓜皮的期望次数。
显然可以根据下一个取瓜子还是瓜皮直接 $dp$。
可能需要预处理一下逆元。
时间复杂度$O\left(n^2\right)$。
code

查询第 $k$ 大，一看 $k$ 这么小，显然可以在 $k$ 上动手脚。
一个数要成为第 $k$ 大，那么它左边与它右边比它大的数加起来肯定恰好 $k-1$ 个。
我们不妨将它左边比它大的 $k$ 个数与它右边比它打的 $k$ 个数都找出来，一个一个去匹配区间。
由于只需要看比它大的数，我们可以将所有数从大到小依次加入。
统计每个数时比它大的数都加入了，我们可以用 $set$ 找到它的位置，再用链表将前 $k$ 个与后 $k$ 个都找出来就行了。
时间复杂度 $O\left(n(\log n+K)\right)$。
code

显然，如果一个长度为 $x$ 的路径能与长度为 $y$ 匹配，那么它肯定可以与 $0,1,...,y-1$ 的路径匹配，将这些路径看成长度 $y$ 的一个子路径就行了。
所以我们需要找到一个长度为 $x$ 的路径最长能与多长的路径匹配。
我们可以用换根 $dp$解决这个问题。
我们将路径看成两种，不经过根的路径与经过根的路径。
显然，两条路径不可能都不经过根，因为它们不相交
我们可以枚举一个不经过根的路径的在根的哪一棵子树内，就当成这个子树内最长的哪个路径。
然后找经过根的最长的不经过那棵子树的路径与之匹配。
显然，任意一种路径的组合都存在一种方法可以这样划分，所以这样肯定是合法的。
只是在每个点上都要将所有点的 $dp$ 值排序，有一个 $\log n$。
时间复杂度 $O\left(n\log n\right)$，其实可以用优先队列只维护前 $3$ 大的 $dp$ 值，做到 $O\left(n\right)$。
code

最难的是读题，不过我改过的题面应该很清晰了。
容易想到做法肯定是贪心的做法。
我们可以用单调队列维护现在还未购买，之后可以购买带过来的糖果有哪些。
显然，我们对糖果的操作主要有两种。

• 卖掉当前的糖果换钱。
• 在路途上花费当前的糖果。

显然第二类操作是会贡献到答案的，我们肯定是尽可能的用越便宜的糖果，所以我们只需要将队列的前几个代价小的糖果用掉，在下一个点再将用掉的糖果补上。
到下一个点队列里存的就代表现在还未买到，但可以买的糖果，显然，如果队列里有大于 $b_i$ 的糖果，我们肯定是可以将其换成 $b_i$ 的糖果，让之后的代价最小。
如果有小于 $s_i$ 的糖果，我们可以将它卖掉，换成钱，也就是 $s_i-b_j$ 的资金。
我们可以再往我们的单调队列中加入一个 $s_i$的糖果，表示我们的反悔操作。
如果这个 $s_i$ 的糖果被用掉了，那显然就是反悔了，还是花了 $b_j$ 的钱，如果被换成其它的糖果，那就是赚了钱。
由于我们每次修改的都是一段前后缀，所以显然是可以用单调队列维护的。
注意 $C⩽10^3$ 糖果可能很多，但种类实际上是很少的，我们可以像 $ODT$ 一样往单调队列里塞线段，这样总的时间复杂度就可以做到 $O\left(n\right)$ 了。
code